算法時(shí)間復(fù)雜度的計(jì)算-資料下載頁
2025-07-26 09:45本頁面
【正文】 。 T(n) = 2+4n f(n) = n lim(T(n)/f(n)) = 2*(1/n) + 4 = 4 T(n) = O(n). O(log2n) i=1。 ① while (i=n) i=i*2。 ②解： 語句1的頻度是1, 設(shè)語句2的頻度是t, 則：nt=n。 t=log2n 考慮最壞情況，取最大值t=log2n, T(n) = 1 + log2n f(n) = log2n lim(T(n)/f(n)) = 1/log2n + 1 = 1 T(n) = O(log2n)O(n3) for(i=0。in。i++) { for(j=0。ji。j++) { for(k=0。kj。k++) x=x+2。 } }解：當(dāng)i=m, j=k的時(shí)候,內(nèi)層循環(huán)的次數(shù)為k當(dāng)i=m時(shí), j 可以取 0,1,...,m1 , 所以這里最內(nèi)循環(huán)共進(jìn)行了0+1+...+m1=(m1)m/2次所以,i從0取到n, 則循環(huán)共進(jìn)行了: 0+(11)*1/2+...+(n1)n/2=n(n+1)(n1)/2次T(n) = n(n+1)(n1)/2 = (n3n)/2f(n) = n3所以時(shí)間復(fù)雜度為O(n3)。
物理相關(guān)推薦
鄂ICP備17016276號-1