big-o - (log n)^k = O(n^1/2) ですか? k が 0 以上の場合

Question

big-O 表記では is 、定数はO((log n)^k) = O(log n)どこにありますか? では、 whenkで何が起こっているのでしょうか?(log n)^kk>=0

Answer 1

これが誤解の元になっているのではないでしょうか？log(n^k) = k * log(n) ですが、そのような単純化は log(n)^k = (log(n))^k では機能しません。

Answer 2

O((log n) * k) == O(log n) ですが、(log n)^k はまったく同じではありません。私はあなたが大きなO表記と同等の定数乗算を考えていると思います。ただし、f(n) を累乗すると、完了までの時間が変わります。これは、O(n) が O(n^2) と異なるのと同じ概念です。