困惑於大O符號

好吧我有一個快速的問題，所有的程序員都在爲一個簡單的問題進行預設。困惑於大O符號

對於我的計算機科學II類，我們要通過Big-Oh表示法，並且我已經掌握了大部分內容，但我仍然對示例的某些語義感到困惑。

這裏的一切都是用Java編寫的。

我的教授在課堂上給了我們這些例子，但我的運氣，我沒有寫下答案。

一個）

int count = 0; 
    for (int i = 1; i <= n; i++) 
     for (int j = n; j > 1; j----) 
      for (int k = 1; k < n; k = k + 2) 
       count++;

B）

int count = 0; 
for (int i = 1; i <= n; i++) 
    for (int j = n; j > 1; j----) 
     for (int k = 1; k < 1000; k = k + 2) 
      count++;

C）

int count = 0; 
    for (int i = 1; i <= 1000000; i++) 
     for (int j = i; j > 500; j----) 
      for (int k = 1; k < 10500; k = k + 2) 
       count++;

d）

int count = 0; 
int j = 1; 
for (int i = 1; i < n; i++) { 
     while (j < n) { 
      j++; 
      count++; 
     } 
     j = 1; 
    }

E）

int count = 0; 
int i = n; 
while (i > 1) 
{ 
    count++; i = i/2; 
}

好的所以這裏是我的答案/思維過程：

一個）N * N *（N/2）= N^3/2，所有簡化爲一個O（N^3）符號

二）N * N * 500，全部簡化爲O（N^2）

C）這是我majorly困惑你有三個for循環的一個，但所有迭代的確切數目倍。在這裏，我的猜測是O（1），但我不知道......

d）N * N = N^2，所以O（N^2）

E）除以一半每一次，所以log（n）= O（log（n））[base 2]

所以任何人都可以檢查我的思維過程，看看我是否失去了什麼？提前感謝你！

來源

2012-02-10 BlueLink77

大O不大哦... – 2012-02-10 05:56:04

大哦意味着別的東西完全。 SO的主題不在話下。 :) – cHao 2012-02-10 05:58:16

糟糕：P不知道。謝謝一堆！ – BlueLink77 2012-02-10 06:11:29

是（C）是O（1），因爲它都是常量。

來源

2012-02-10 05:59:11 Dan

在所有這些示例中，count對於每個工作單元都增加一次。如果你能找出count和n之間的關係，那麼你就知道程序的漸近順序。

這是很好，你工作的事情。下一步是檢查你的計算與現實。運行代碼n的不同值，打印出count，並根據實際數據檢查您的工作。

來源

2012-02-10 06:02:04

困惑於大O符號

回答

相關問題