[解決済み】8歳児にビッグ・オー？[重複あり］

質問

私は、これが私のコードにとってどのような意味を持つのかについて、より詳しく尋ねています。 数学的には理解しているのですが、概念的に何を意味しているのかがよくわからないのです。 例えば、あるデータ構造に対してO(1)の演算を行う場合、項目が多いから演算の数が増えないというのは理解できるのですが。 そして、O(n)演算とは、各要素に対して一連の演算を行うということですね。 どなたか、この空白を埋めていただけませんか？

• O(n^2)演算は具体的に何をするのでしょうか？
• また、ある演算がO(n log(n))であるとは、一体どういうことなのでしょうか？
• また、O(x!)を書くには、誰かがクラックを吸わなければならないのでしょうか？

解き方は？

ひとつの考え方として、こういったものがあります。

O(N^2)とは、すべての要素について、他のすべての要素との比較など、何かを行っていることを意味します。 バブルソートはその一例です。

O(N log N)とは、すべての要素に対して、対数Nの要素だけを見る必要があることを意味します。 これは通常、要素について何か知っているため、効率的な選択をすることができます。 マージソートのような効率的なソートは、この例です。

O(N!)とは、N個の要素のすべての可能な並べ換えに対して何かをすることです。 トラベリングセールスマンはこの例で、ノードを訪問する方法がN！通りあり、ブルートフォースソリューションは、最適なものを見つけるために、すべての可能な順列の総コストを調べることである。