各種嵌套for循環的時間複雜性

Question

時間如果循環變量被劃分/乘以常量，則循環的複雜性被視爲O（Logn）。

環1 ----

for (int i = 1; i <=n; i *= c) 
{ 
    // some O(1) expressions 
} 

環2 -----

for (int i = n; i > 0; i /= c) 
{ 
    // some O(1) expressions 
} 

時間的循環的複雜性被認爲是O（LogLogn）如果循環變量被降低/以恆定的數量呈指數增長。

Here c is a constant greater than 1 

環3 ----

for (int i = 2; i <=n; i = pow(i, c)) 
{ 
    // some O(1) expressions 
} 

迴路4 -----

////Here fun is sqrt or cuberoot or any other constant root 
for (int i = n; i > 0; i = fun(i)) 
{ 
    // some O(1) expressions 
} 

任何人都可以解釋我爲什麼它是考慮的次數內循環在這些循環中執行？

如果在循環1和循環2中c = 1，那麼它將無限次地運行正確，但它是以對數時間給出的原因？

它是如何O（loglogN）在循環3和循環4？

Answer 1

如果在循環1和循環2中c = 1，那麼它將無限次地運行正確，但它是以對數時間給出的。

是的，你是對的，如果c = 1那麼我們將獲得無限循環兩種情況1和情況2，因此條件「c是一[整數]常數大於1」還需要兩個情況1和情況2，以便獲得O(log n)的複雜性。

---

對於情況1，注意i取值1, c, c2, c3, ..., clogc(n)，所以總共有log(n)多次迭代，以及對於每次迭代存在要完成（即O(1)工作的量）的工作的一個恆定量，所以總工作量爲log(n) * O(1) = O(log(n))。

類似地，對於殼體2，i取值n, n/c, n/c2, n/c3, ..., , n/clogc(n)，所以總共有log(n)許多迭代和每次迭代花費的時間常數量，所以總的時間複雜度是O(log(n))。

對於情況3,i取值2, 2c, (2c)c = 2c2, (2c2)c = 2c3, ..., 2clogc(log(n))。最後一項必須小於或等於n，我們有2clogc(log(n)) = 2log(n) = n，這證明了我們上一期的價值。所以總共有很多次迭代，每次迭代需要一定的時間，因此總的時間複雜度爲O(log(log(n)))。

類似地，對於殼體4，i取值n, n1/c, (n1/c)1/c = n1/c2, n1/c3, ..., n1/clogc(log(n))，所以總共有logc(log(n))迭代和每一次迭代花費時間O(1)，所以總的時間複雜度是O(log(log(n)))。