標籤：

簡單的時間複雜度問題.一到log這就不會了. 誰能給我講講啊?

01-15

int num1, num2;

for(int i=0; i&

語句j&<=n; j*=2; num2+=num1;的頻度為n*log2n；

為什麼是Log2n啊?

j&<=n, j= j*2,那麼?j*2&<=n.j&<=n/2?不是這樣算, 不是這樣算. 那麼是怎麼算能算出來log來啊. 高中數學都忘了啊.......

怎樣簡單的計算出時間複雜度啊...我覺得時間複雜度如果數學好一點應該是一看就知道結果的...

j 每循環一次乘了 2.

j 初始為 1，所以循環 x 次之後 j=2^x.

j > n 時停止循環，也就是 2^x > n，此時x=log_{2}^{n}.

所以 j 循環了 log_{2}^{n} 次.

for(int j=1; j&<=n; j*=2)

這個循環最終執行的次數假設為x，則x次的時候j=2^x

當j&>n時停止執行，於是2^x&>n 則可以認為該循環一共執行了log2(n)次

所以該循環的時間複雜度為o(log2(n))簡記為o(log n) 忽略掉2的底數

維基百科中：

主條目：對數時間

若演算法的 T(n) = O(log n)，則稱其具有對數時間。由於計算機使用二進位的記數系統，對數常常以10為底（即log10 n，有時寫作 lg n）。然而，由對數的換底公式，loga n和 logb n只有一個常數因子不同，這個因子在大O記法中被丟棄。因此記作O(log n)，而不論對數的底是多少，是對數時間演算法的標準記法

先說num2+=num1的頻度吧，看起來不知道，不妨設頻度為k（f(n)=k），因為每次自變數為上次步進的2倍，則有 2^k &>n,取近似值得到k=log2n，即f(n)=log2n。又外循環num1+=1的頻度為n，所以num2+=num1的頻度n*long2n，所以總的時間複雜度為n+n*log2n，取變化最快的項，即n*log2n

恩恩，如果不看循環內執行語句，單單看循環本身的話，這個問題是不是就很好理解。

首先，我們來看外循環for（i=0；i&再來看看內部循環，for（j=1；j&n===》x=log(2)N

ps:(2)代表底數，請原諒我打不出正確的數學符號，sorry

如果把兩個循環合在一起看的話，也就是一共循環了n個x次，也就是n*log(2)N

for(int j=1; j&<=n; j*=2){

num2 += num1;

}

如果這層是 j++; 那麼時間複雜度是 n^2 . 因為這層需要n 次(j需要自增n次 才能滿足 j&<=n )

如果是 j*=2; 那麼需要多少次能滿足 j&>=n . （j初始為1）2^x=n .

x=log2^n 所以 。所以這層需要 log2^n次。時間複雜是 n*log2^n.

題主，j=j*2是要乘很多次，不是一次，所以其實最後的條件是n&>j*2*2*2*2……*2。那麼假設乘了x次吧，這時候n&>2^x，那麼x就是log n，也就是那個循環的複雜度。

另外題主如果是這個程度的數學都不會…你要不要考慮轉文科（逃

推薦閱讀：

※數據結構的那些排序演算法總是記不住，這個真的背的嗎？
※C 和 C++ 值得深入學習嗎？
※C++ 自己寫一個更好的 string 需要什麼步驟？
※C++樹結構實現中，為什麼要單獨定義節點類？

TAG:演算法 | 時間複雜度 | 數據結構 |