algorithm - この for ループ ステートメントの実行時間は?

Question

このループ ステートメントの Big-O 実行時間を把握しようとしています。誰か助けてくれませんか？

for (i = 1; i < n*n; i=i*2)

ですかO(n^2 lg n)？

Answer 1

そのO（logn）：

log(n^2) = 2log(n) = O(logn) 

Answer 2

いいえ、そうあるべきですO(logn)。なぜならlog(n^2) = O(logn)。

Answer 3

提案された答えは正しいです。これはO(logn)、反復インクリメントが多項式 (1、4、8、16 など) であり、線形ではないためです。

このように見ることができます - 反復の数は線形ではなく、反復の量に対数的に比例する多項式です。反復回数は 2 次ですが、ループの実行中は一定であるため、量指定子2は2*O(logn)無視できます。