時間複雜度練習（僞代碼）

Question

剛開始的數據結構。被困在這一個：

我有內部while和for循環的麻煩，因爲它的變化，如果數值N是奇數還是偶數。

我最好的情況下，將是 - 內部的循環運行LOGN（基數爲2）次， 而while循環 - LOGN倍（基數爲2）

很想一些幫助。

Answer 1

專注於調用do_something()多少次。

外for環清楚運行n倍，while循環內它是獨立可變的i。因此do_something()被稱爲n倍於在while循環中調用的總次數。

在第一次通過while循環時，do_something()被調用一次。在第二時間，它被稱爲兩次，第三次的叫法，4倍等

的時候，它被稱作總數因此是

1 + 2 + 4 + 8 + ... + 2^(k-1) 

其中k是最大的，使得2^(k-1) <= n。有上述總和的標準公式。使用它，然後根據n解決k，並將結果乘以外循環中的n，然後完成。