big-o - 这些简单循环的时间复杂度是如何计算的？

Question

我了解如何：

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

这个时间复杂度是O(n)。

for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
        for (k=0; k<n; k++)

这是O(n^3)对的吗？

i=1
do
    //......
    i++
while (i*2 <n)  

这是O(n)吗？或者是这样O(n/2)吗？

Answer 1

O(n/2) 仅 O(n)具有 1/2 的常数系数。系数可以是 100 亿，它仍然是O(n)，而不是例如O(n^(1.0001))哪个是不同的复杂度类。

Answer 2

O(n ³ )的第一个，你是对的。

您的第二个算法是O(n/2) = O(Cn) = O(n)。1/2是一个常数，所以我们可以安全地丢弃它。

Answer 3

第一个复杂度 O(n^3)，正确。第二个，O(cn)，c 常数。不管c有多大，按照big-O的定义，复杂度还是O(n)。

然而，O-notation 被认为是有害的。见这里。

Answer 4

这段代码：

i=1
do
    //......
    i++
while (i*2 < n);

相当于那个：

for ( i = 1; i < n / 2 ; ++ i );

从表面上看，这是O(n).