與決定大O符號混淆？

所以，我真的不會得到大O符號。我的任務是確定這個代碼段的「O值」。與決定大O符號混淆？

for (int count =1; count < n; count++) // Runs n times, so linear, or O(N) 
    { 
     int count2 = 1;  // Declares an integer, so constant, O(1) 

     while (count2 < count) // Here's where I get confused. I recognize that it is a nested loop, but does that make it O(N^2)? 
      { 
       count2 = count2 * 2; // I would expect this to be constant as well, O(N) 
      } 
    }

來源

2013-10-19 user2896852

將O-notation想象成「我能以多快的速度」問題。並且它爲嵌套操作乘法複合。外循環：在'n'複雜度中'count''到那裏。內部循環：'count2'''在那裏''logN'的複雜性（每次迭代你都加倍）。這是'O（nlogn）' – WhozCraig

好的WhozCraig，這是有道理的。謝謝你的幫助。 – user2896852

@WhosCraig - 爲了澄清，大O不*嚴格地關於速度，或者「我到那兒速度有多快」。它還可以描述功能的空間複雜性等等。 – GraphicsMuncher

O(f(n))=g(n)

這意味着，對於一些價值k，f(n)>g(n)其中n>k。這給出了功能g(n)的上限。

當你被要求找到Big O一段代碼，

1）儘量計數的n方面，從而獲得g(n)執行計算的數量。

2）現在嘗試估計g(n)的上限函數。這將是你的答案。

讓我們把這個程序應用到你的代碼中。

讓我們計算所做的計算次數。陳述declaring和multiply by 2取O(1)時間。但是這些被反覆執行。我們需要找出他們執行了多少次。

外循環執行n次。因此第一條語句執行n次。現在內循環執行的次數取決於值n。對於給定值n它執行logn次。

現在讓我們來算執行的計算總數，

log(1) + log(2) + log(3) +.... log(n) + n

注意最後n是第一個發言。簡化上述系列中，我們得到：

= log(1*2*3*...n) + n 

= log(n!) + n

我們有

g(n)=log(n!) + n

讓我們猜上限log(n!)。

因爲，

1.2.3.4...n < n.n.n...(n times)

因此，

log(n!) < log(n^n) for n>1

這意味着

log(n!) = O(nlogn).

如果你想爲這個正式的證明，檢查this出來。由於nlogn增長快於n，因此，我們有：

O(nlogn + n) = O(nlogn)

因此你最後的答案是O(nlogn)。

來源

2013-10-19 03:52:27 nitish712

與決定大O符號混淆？

回答

相關問題