私は、挿入ソートアルゴリズムでバイナリ検索を使用することについて簡単な質問があります。より正確には、通常の挿入ソートの各ステップで、以前の（ソートされた）サブアレイ内のすべての要素と線形比較するのではなく、そのソート済みサブアレイ内のバイナリ検索を使用して、バイナリの挿入の並べ替えと複雑さ
これは、アルゴリズムが（O（n）の代わりにO（log n））の比較回数を減らしたが、各ステップで必要なスワップの数が依然として支配的であり、^2）。
また、複雑さは実行時間にあまり関係しないことも知っています。私は両方のアルゴリズムの実行時間をn（配列サイズ）の「小さな」値、約500000まで比較しようとしました。バイナリの挿入の並べ替えは、通常の挿入の並べ替えよりも常に高速でした。
両方がO（n^2）であるという事実は、nが十分に大きくなると、実行時間も同様でなければならない、ということを私に伝えます。このような状況で、実際に同じような稼働時間が見られるようにするには、「十分な大きさ」とは何かに関する考えはありますか？
O（n^2）ということは、nが十分に大きくなると、実行時間も同様でなければならない、ということです。
注意 - これは間違っています。 n^2と2n^2は、nが大きくなるにつれて互いに近づくことはありません。彼らはさらに離れていく。しかし、どちらもO(n^2)です。
あなたの両方のアルゴリズムがO(n^2)であるとはどういう意味ですか？まあ、最終的には、それぞれがn^2の何らかの定数倍で上に束縛されることを意味します。バイナリの挿入ソートの場合は10n^2、標準挿入の場合は1000n^2となります。両方ともn^2ですが、効率は100（この例では）の係数によって異なる場合があります。
複雑さは、特定の関数の動作について、その関数が他のものとどう積み重ねるかについてよりも詳しく説明します。たとえば、機能がO(n^2)であることがわかっている場合は、nという大きな値の場合、の一定の時間だけ、f(n+1)が大きくなることがわかります（の派生値は2nです。連続項間の差は直線的に増加する）。
それは素晴らしい説明であり、私の誤解を明確にするのに役立ちます。 – dbluesk
理論的には、バイナリの挿入ソートの複雑さはO（log_2（n！））、 Wolframalphaです。
これはO（n²）とO（n log（n））の間にあり、実際にはO（n log（n））の近くにあります。
実際には、nが十分に大きくなると、実行時間は似ているはずはありません。つまり、nが無限に近づくと、両者はほぼ同じ速度で無限の実行時間に近づくことになります。 –