困惑于大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]
所以任何人都可以检查我的思维过程,看看我是否失去了什么?提前感谢你!
答
是(C)是O(1),因为它都是常量。
答
在所有这些示例中,count
对于每个工作单元都增加一次。如果你能找出count
和n
之间的关系,那么你就知道程序的渐近顺序。
这是很好,你工作的事情。下一步是检查你的计算与现实。运行代码n
的不同值,打印出count
,并根据实际数据检查您的工作。
大O不大哦... – 2012-02-10 05:56:04
大哦意味着别的东西完全。 SO的主题不在话下。 :) – cHao 2012-02-10 05:58:16
糟糕:P不知道。谢谢一堆! – BlueLink77 2012-02-10 06:11:29