異なる複雑さで同じ結果を計算する2つのalgorthimがある場合、O(log n)は常により速くなりますか?もしそうなら、説明してください。これは割り当ての問題ではありません。O(log n)は常にO(n)よりも速いですか
10
A
答えて
23
いいえ1つのアルゴリズムがN/100
で実行され、もう1つのアルゴリズムが(log N)*100
で実行される場合、2番目のアルゴリズムは入力サイズが小さいほど遅くなります。漸近的複雑さは、入力サイズが無限になるまでの実行時間の振る舞いに関するものです。
12
いいえ、必ずしも高速であるとは限りません。しかし、問題のサイズが大きくなるにつれて、の最終的には、O(log n)アルゴリズムがO(n)より速い点に常に到達します。
通常、O(log n)アルゴリズムがO(n)アルゴリズムを追い越すポイントは、非常に迅速になります。 O(n)とO(n^2)の間に大きな違いがあるように、O(log n)とO(n)の間には大きな違いがあります。
あなたはジョン・ベントレーによってプログラミング真珠を読む機会を持っている場合は、そこに素晴らしい章彼はに可能なすべてをやって、O(n)のOに対するアルゴリズム(N^2)1ピットがありますO(n^2)に利点を与える。 (彼は、Alpha上でC言語でO(n^2)アルゴリズムをコーディングし、古いZ80などでは約1MHzでBASICを解釈するO(n)アルゴリズムをコーディングしています)アルゴリズムはO(n^2)を追い越します。
場合によっては、非常に複雑なアルゴリズムがありますが、複雑なアルゴリズムは、単純なものよりわずかに優れています。そのような場合、盲目的にアルゴリズムを選択しないでください。大規模な問題で高速に処理されることがあります。
関連する問題
- 1. バイナリ検索はO(log n)かO(n log n)ですか?
- 2. O(n)とO(log(n))の違い - これはより良く、O(log(n))は正確に何ですか?
- 3. log(n!)= O((log(n))^ 2)ですか?
- 4. ログ(O(n * log(n)))は何ですか?
- 5. O(1)、O(n log n)、O(log n)の複雑さを持つアルゴリズムの例
- 6. 複雑さO(log(n))はO(sqrt(n))と等価ですか?
- 7. O(n^2 * log(n))とO(n^3)どちらが大きいですか?
- 8. ListBox.FindString最悪の場合のランタイムは何ですか? O(n)、O(n log n)、O(1)?
- 9. すべてのn、O(1)がO(n)よりも速い場合、O(1)上でO(n)を選択しますか?
- 10. O(log N)intよりJavaより速く実装できますか?
- 11. 床(√2n)のO(log log n)アルゴリズム?
- 12. O(n)vs O(n^2)
- 13. O(3^log n)をO(n^log 3)として書き直すことはできますか?
- 14. O(n * log n)の仕事をし、O(n^2)の仕事をするコードの複雑さは何ですか?
- 15. 関数2log(log(n))+ 3nlog(n)+ 5log(n)のbig-oとは何ですか?
- 16. o(n^2)の代わりにo(log n)またはo(n)の時間複雑度を持つようにこのコードを修正する方法
- 17. なぜこのO(n^2)ソリューションはO(n)ソリューションより速く動作するのですか?
- 18. なぜO(n * logn)ではなくTreeSet Iteration O(n)ですか?
- 19. O(log n)のバイナリ検索ツリー?
- 20. f(n)= log(n)^ mはすべての自然数mに対してO(n)
- 21. 時間複雑度がO(sqrt(n)* log(n))のアルゴリズムはありますか?
- 22. O(N)Oまで(LOGN)
- 23. O(n log n)時間での線配置の境界ボックス
- 24. O(n)
- 25. T(n)= 2T(n/2)+ O(n)からO(nlogn)を得る方法
- 26. O(m + n)かO(mlgn)が良いか
- 27. 漸近分析では、 - O(f(n)+ g(n))= O(max {f(n)、g(n)})
- 28. f(n)= 1000n + 4500lgn + 54n O(n)ですか?
- 29. O(n)ソートアルゴリズム
- 30. Javascript:解決策をO(n log n)に変更してください
十分な大きさ* n *の方が常に高速です。 – Phonon