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 ³ )の最初のもの、あなたは正しいです。

2 番目のアルゴリズムはO(n/2) = O(Cn) = O(n)です。1/2は定数なので、安全に破棄できます。