1

重複の可能性：
BigOのわかりやすい英語の説明

対数関数的成長に関するウィキペディアの記事はスタブです。私がstackoverflowで読んだ回答の多くは、プロセスまたは関数が使用する対数関数に基づいてどれほど効率的であるかを明確にしています0（[以下を参照]これは0 [ゼロ]であり、O [M、N、Oとしての文字ではない] 、P、Q]ですが、間違っている場合は私の仮定を修正してください）およびnまたはN。

誰かが一般的な計算の説明に関連する対数の説明をよりよく説明できますか？おそらく秒単位の時間（ミリ秒も歓迎します。実際の時間の違いで概念化しようとしているだけです...）、サイズ、および/または重量の観点からですか？

私は次のことを頻繁に見ました:(他のものも含めてください）

  • O（1）
  • オン）

私の仮定は、コードブロックの外側の0 [ゼロ]にはスラッシュがないが、inside a code block a 0 does have a slash through it。

4

1 に答える 1

1

これが意味することは、実行時間 (または他のリソース) がデータ量の関数であることです。風船を 10 個爆破するのに 5 分かかるとしましょう。関数が O(1) の場合、50 個の風船を爆破するのにも 5 分かかります。O(n) の場合、50 個の風船を爆破するには 25 分かかります。

O(log n) は、物事がスケールアップするにつれて、より大きな n の管理が容易になることを意味します (対数的成長に従います)。f(n) 項目のディレクトリでアドレスを検索したいとしましょう。100 エントリのディレクトリを検索するのに 6.64 秒かかるとします。[6.64 = log_2(100)] この場合、200 エントリを検索するのに 7.64 秒しかかからない可能性があります。それが対数的成長です。

于 2012-12-03T09:01:05.037 に答える