「隠れ定数」とは何ですか？

Question

アルゴリズムの比較時に多くの人が話しています。たとえば、quicksortとsmoothsortを比較すると、どちらも平均時間複雑度はO（nlogn）ですが、「隠れ定数が多い」ためsmoothsortが最悪です。

これはどういう意味ですか？

Answer 1

アルゴリズムの実行時間を分析すると、定数乗算器が削除されます。たとえば100*nはO(n)と表記されていますので、3*nとなります。誰かが「隠れた」定数について話すとき、無視されたこれらの乗数について話しています。

それだけではなく「隠された」定数はだけでなく、運用コストを大幅に実際実行している時間に影響を与えることは注目に値します。たとえば、10分割と割り当てには20回以上の追加が必要です。