困惑于大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符号

回答

相关问题