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)) 这是一个不同的复杂度类。