找到循環的複雜性

Question

我給了這個算法，我被告知找到它的大θ複雜性。

for (i = 1; i <= n; i++) { 
    j = n; 
    while(j >= 1) { 
     j = j/3; 
    } 

} 

我知道outer for循環運行n次。雖然while循環比較棘手，但它可能是log n（基數爲3）。共計n * log n

這是正確的嗎？

Answer 1

有一個外部for循環的大小爲n。它在整個複雜度上貢獻了因子n的複雜性。

假設inner while循環運行m次。在第i次迭代之後，j的值將是n /（3^i）。我們將運行這個直到N /（3^I）> 1。因此，

=> n/(3^i) = m 
=> n = 3^m 
=> log(n) = log2(3) * m 
=> m = O(log(n)) 

所以，對於循環有助於O（n）和while循環有助於O（日誌（N））。嵌套循環的複雜性變爲O（n log（n））。