中南大學數(shù)據(jù)結(jié)構(gòu)與算法-第1章緒論課后作業(yè)答案(編輯修改稿)
2025-08-19 23:26 本頁面
【文章內(nèi)容簡介】 ≤T（n）≤Cf（n）。 通俗地說，就是當n→∞時，f(n)的函數(shù)值增長速度與T（n)的增長速度同階。一般，一個函數(shù)的增長速度與該函數(shù)的最高次階同階?！〖矗骸 (f(n))=n3 O(g(n))=n3 O(h(n))= 所以答案為：答： ●（1）成立?！ 瘢?）成立?！ 瘢?）成立?！ 瘢?）不成立。 設(shè)有兩個算法在同一機器上運行，其執(zhí)行時間分別為100n2和2n,要使前者快于后者，n至少要多大?分析： 要使前者快于后者，即前者的時間消耗低于后者，即： 100n22n 求解上式，可得答： n=15 設(shè)n為正整數(shù)，利用大O記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)。(1) i=1。 k=0?！ hile(in) { k=k+10*i。i++。 }分析： i=1。 //1 k=0。 //1 while(in) //n { k=k+10*i。 //n1 i++。 //n1 }由以上列出的各語句的頻度，可得該程序段的時間消耗： T(n)=1+1+n+(n1)+(n1)=3n可表示為T(n)=O(n)(2) i=0。 k=0。 do{ k=k+10*i。 i++?！ while(in)。分析： i=0。 //1 k=0。 //1 do{ //n k=k+10*i。 //n i++。 //n } while(in)。//n由以上列出的各語句的頻度，可得該程序段的時間消耗： T(n)=1+1+n+n+n+n=
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1