查找此代碼的大O

我需要一些幫助來查找此代碼的複雜性或Big-O。如果有人能夠解釋每個循環的Big-O會是什麼，那將是很棒的。我認爲outter循環只是O（n），但我不確定內部循環，* = 2是如何影響它的？查找此代碼的大O

k = 1; 

do 
{ 
    j = 1; 
    do 
    { 
     ... 
     j *= 2; 
    } while (j < n); 

    k++; 
} while (k < n);

來源

2015-10-09 user4892930

外部循環運行爲O（n）次，由於k從1開始，需要遞增N-1次，成爲等於1

內環運行O（LG（正））次。這是因爲在循環的第m次執行時，j = 0.5 * 2 ^（m）。

當n = j = 0.5 * 2^m時，循環中斷。重新排列它，我們得到m = lg（2n）= O（lg（n））。將兩個循環放在一起，總代碼複雜度爲O（nlg（n））。對數可能非常棘手，但通常情況下，無論何時您看到某個東西被重複乘以或除以常數因子，您都可以猜測算法的複雜性涉及對數或指數的項。

這就是爲什麼binary search，它重複劃分它搜索的列表大小的一半，也是O（lg（n））。

來源

2015-10-09 03:55:54

內循環始終從j=1運行到j=n。

爲簡單起見，我們假設n是2的冪，並且內部循環運行k次。

這意味着2^k = n或k = lg(n)

所以，每一次，它運行O(lg(n))次的j每個k迭代的值，

j = 1 
j = 2 
j = 4 
j = 8 
.... 
j = n 
// breaks from the loop

。

現在，外循環執行O(n)次，從k=1開始到k=n。

因此，每當k遞增時，內循環運行O(lg(n))次。

k=1 Innerloop runs for : lg(n) 
k=2 Innerloop runs for : lg(n) 
k=3 Innerloop runs for : lg(n) 
... 
k=n Innerloop runs for : lg(n) 
// breaks from the loop

因此，採取的總時間是n*lg(n)

因此，這樣做的時間複雜度是O(nlg(n))

來源

2015-10-09 04:31:57 GokulSrinivas

查找此代碼的大O

回答

相關問題