O =（N²）は10回実行すると遅くなりますか？

Question

私は2つのforループを持っています。つまり、O =（N²）という意味です。 Nが5000の場合、25000000（1回実行された場合）となります。一度これを実行すると正しいことになりますが、私が10回実行すると、はるかに多くのステップが必要になります。これは起こるはずですか？

Answer 1

big-O表記はアルゴリズムの漸近的なステップ数を記述するためのものです。これは、大きな入力に対して異なるアルゴリズムを比較するためのものです。例えばヒープソートとソートマージO（NログN）です。従って、それらは漸近的に速くより小さいの挿入種別（n^2）にある挿入種別です。

同じアルゴリズムを実行すると、定数は変わりませんが、big-Oクラスは単なる推定値であり、ステップ数の正確な尺度ではありません。このように、あなたのアルゴリズムは25,000,000の手順が正しくあってはならない必要と言って（例えばN（N - 。。1）/ 1,000,000は、あまりにもO（のn^2）、です）。