大きなああ表記を理解しようとしています。どんな助けでも大歓迎です。
最大ヒープを作成し、アイテムをプッシュして削除するプログラムがあるとします。
n個のアイテムがあるとします。
ヒープを作成するには、配列に読み込んでからヒープ化した場合、ヒープ化に O(n) かかります。アイテムをプッシュするには O(1) かかり、それを削除するには O(1) かかります。
したがって、大きな oh 表記は O(n + n log n) OR であり、O(n log n) というのは、最大のものを選択したからに過ぎません。
ヒープ内の新しい要素をヒープ化する複雑さはそうではO(logN)ありません（そうではないように思われるフィボナッチヒープO(1)を使用しない限り）。
また、より速く成長するための表記法はないO(N + NlogN)ためNlogN、Nこの表記法は単純に。と記述されO(NlogN)ます。
編集：big-oh表記は、関数の漸近的な振る舞い、つまり、関数がどれだけ速く成長するかを説明するだけです。無限大に近づいて同じよう2*f(x)に11021392103*f(x)動作するため、big-oh表記を記述する場合、関数の前にある定数はすべて無視されます。
正式には、O(N + N log N)と同等O(N log N)です。
とはいえ、これらのそれぞれに埋め込まれた係数があると想定されています ala: O( aN + bN log(cN) )。値が非常に大きいN場合、これらの係数は重要ではなくなり、アルゴリズムはその最大項 (この場合は ) によってのみ制限されますlog(N)。
しかし、係数がまったく重要でないというわけではありません。これが、グラフ アルゴリズムの議論で、著者が「Floyd-Warshall アルゴリズムは O(N^3) 時間で実行されますが、係数は小さい」などと言うのをよく目にする理由です。
この場合、どうにかして O(0.5N^3) と書くことができれば、そうするでしょう。しかし、係数は、アルゴリズムの実装方法とそれを実行するコンピューターによって異なることがわかりました。したがって、必ずしもそれが最良の方法であるとは限りませんが、実際には適切な代替手段がないため、漸近比較に落ち着きます。
「最悪の場合: O(N^2)、平均の場合: O(N)」のようなものも表示されます。これは、アルゴリズムの動作が入力によってどのように変化するかを捉えようとする試みです。多くの場合、事前に並べ替えられた入力またはランダムな入力によってその平均的なケースが得られますが、邪悪な悪役は最悪のケースを生成する入力を構築できます。
最終的に、私が言いたいことは次のとおりO(N + N log N)=O(N log N)です。これは真実であり、宿題の正しい答えです。O(N + N log N)しかし、私たちはこの big-O 表記法を使用して通信を行っており、時間の経過とともに、アルゴリズムが一般的に small に使用されている場合、それがより表現力豊かであると感じる状況が見つかるかもしれませんN。この場合、形式主義についてあまり心配する必要はありません。形式で何を伝えようとしているのかを明確にしてください。