big-O 表記法ではO((log n)^k) = O(log n)、 is はどこkにあるのでしょうか (たとえば、ループの対数の数)、真ですか?
私は教授から、この声明は真実であると言われましたが、コースの後半で証明されると彼は言いました。誰かがその有効性を実証できるか、それが真実かどうかを確認できるリンクを持っているかどうか疑問に思っていました.
質問する
6980 次
3 に答える
8
（1）O（log（n ^ k））= O（log n）であることは事実です。
（2）O（log ^ k（n））（O（（log n）^ k）とも表記）= O（log n）であるというのは誤りです。
観察：（1）nmjohnによって証明されています。
演習：証明（2）。（ヒント：f（n）= log ^ 2 nはO（log ^ 2 n）です。それはO（log n）ですか？n0より大きいすべてのnについて、c log n>となるのに十分な大きさの定数cは何ですか？ log ^ 2 n？）
編集：
関連するメモとして、この質問が役に立った、または興味深いと思った人は、新しい「コンピュータサイエンス」StackExchangeサイトへの愛情を示してください。ここにリンクがあります。この新しい場所を現実のものにしてください！
于 2012-01-10T20:12:18.923 に答える
5
それは O(k*log n) = k*O(log n) = O(log n) に等しいからです。
于 2012-01-10T19:27:41.660 に答える
-1
O(log n ) は関数のクラスです。^ kなどの計算は実行できません。したがって、O(log n )^ kという用語は、私には意味がないようにも見えます。
于 2012-01-10T19:27:47.153 に答える