分析這個函數的時間複雜度

Question

假設do_something是O（1），我該如何計算這個函數的時間複雜度？

function run(n) { 
    for(var i = 1; i <= n; i++) { 
    var counter = 1; 
    while(counter <= n) { 
     for (var j = counter; j >= 1; j--) { 
      do_something(); 
     } 
     counter = counter * 2; 
    } 

    } 
} 

我假設循環的初始意味着複雜度將是n，內部while循環意味着log（n）。這是真的？

如何計算一切的複雜性？ 謝謝。

Answer 1

計算一切複雜性並不是微不足道的，因爲存在沒有確切分析已知的函數（例如collat​​z猜想）。在這種情況下，你可以做一個經驗分析，你猜猜哪個運行時間等級最匹配。

關係到你的樣品：

1. for循環外被稱爲n次
2. while循環被稱爲的log（n）次
3. 內的循環，其中計數器的增長被稱爲櫃檯倍2^M。但計數器是重新計算的log（n）次

這意味着循環（2^m）的內部指數被稱爲m = log（n）次。 所以你有2 ^（log n）= n log（2）= n

你也可以做反之亦然。內部指數函數稱爲日誌時間。表示log（2^m） - >（2^n = 2^m） - > m = n。

您還可以簡單地創建從m = 0到m = log（n）的2^m之和，即2n-1 - > O（n）。

然後，您必須將outer for loop的線性時間乘以while循環的線性時間（包括inner for loop）。所以你有O（n * n）= O（n²）時間。

Answer 2

可以計算確切的步驟數量。

1. 外部循環運行Ñ倍
2. 的同時和最內循環運行計數器次，每次計數器的值，這些是1, 2, 4, 8, ..., 2^(bitLength(n)-1) ，其總結於2^bitLength(n) - 1

其中bitLength(n) = trunc(ln(n)/ln(2))+1

這兩個數據相乘，得出臺階的確切金額：

n * (2^bitLength(n) - 1)

近似的複雜性是爲O（n ），因爲O(2^bitLength(n) - 1) = O(n)