数か月前の中間期に、次の質問を間違えました。
実験を通じて、あるサイズnの配列をソートするときに、挿入ソートが2000回の比較を実行することを確認します。配列のサイズを3倍にして3nにした場合、およそ何回の比較が実行されますか？
A. 6000
B. 12000
C. 18000
D. 36000
E.配列の内容によって異なります
挿入ソートがO（n ^ 2）であることを考えると、私はC、18000を選択し、間違ってマークされました。
私はそれをこのように推論しました：n ^ 2 = 2000、=> n = 〜44。44 * 3 = 134、134 ^ 2 = 18000
正解はどれですか、そしてその理由は何ですか？
挿入ソートはO(n^2)最悪の場合とO(n)最良の場合です。
新しい要素を挿入するために、挿入ソートは要素の適切な場所を検索します。アルゴリズムが検出する新しい要素が他のすべての要素よりも大きい場合（昇順で並べ替えている場合）、新しい要素ごとに新しい位置を見つけるのに1回の比較のみが必要です。
したがって、配列がすでに並べ替えられている場合、複雑さはO(n)になりますO(n^2)。逆の順序で並べ替えられている場合は、になります。
したがって、正解は次のとおりです。
E.配列の内容によって異なります
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加