这段代码是O（n）还是O（logn）？

它只检查for循环1/3n次，所以它仍然是技术上线性我猜？但是我不明白为什么它不会是O（logn），因为O（logn）运行时间的代码很多时候会检查大约1/3n。 O（logn）总是每次将选项除以2？这段代码是O（n）还是O（logn）？

int a = 0; 
for (int i = 0; i < n; i = i+3) 
    a = a+i;

当您双击* N *，确实次数的循环运行双？还是它添加了一个常量？ – hobbs

你的例子是O（n）;因为它是线性的。考虑类似[二进制搜索]（http://en.wikipedia.org/wiki/Binary_search_algorithm）的对数算法。 –

，这是有道理的hobbs。感谢您的澄清 – user3251142

它为n O(n)的秩序，而不是O(logn)。它因为运行时间的增加，n

欲了解更多信息线性地增加来看看这个图，希望你会明白为什么它不LOGN https://www.cs.auckland.ac.nz/software/AlgAnim/fig/log_graph.gif

2014-03-19 15:25:07 pizzaEatingGuy

运行时间为O(n)（单位复杂性度量）。

2014-03-19 15:25:23 Codor

有了时间复杂性分析，常数因子并不重要。每个循环可以执行1,000,000次操作，它仍然是O（n）。因为常数1/3不重要，它仍然是O（n）。如果您的n为1,000,000，那么n的1/3将比log n大得多。

设k为常数。然后：
O(kg) = O(g) if k is nonzero. 

2014-03-19 15:25:53 rgettman

rgettman，我有一个问题。如果在for循环中，我们有'n = n-2;'在a = a + i之后''？在这种情况下什么是Big-O？ – user3251142

@ user3251142还是O（n）。迭代的次数大约是'n/5'而不是'n/3'（使用'n'的原始值）。我假设你会添加大括号，这样'n = n-2'将成为循环的一部分。 – ajb

问问自己，'for'循环中的迭代次数是否仍然与'n'的原始值成正比。 – rgettman

您的代码复杂度为O（n），O(n)/3 == a * O(n) == O(n)

2014-03-19 15:29:00 user902383

回答