1
私は、クイックソートアルゴリズムの最悪の時間の複雑さを改善するプロジェクトに取り組んでいます。左のほとんどの選択肢の代わりに中央ピボットを選択してアルゴリズムを変更し、特定の反復回数の後に挿入ソートを導入しました。 100000長さ5000のソートされていないデータの入力のためにクイックソート最悪の場合の時間の複雑さ？
：結果は以下の通りである
- クイックソート修正私の中で作られた比較の回数定期的に行われる比較の数よりも非常に少ないですクイックソート。
- データの場合、両方の経過時間はすべての長さでゼロ秒です。 100000長さ5000のすでにソートされたデータの入力のために
：
- 私の修正クイックソートで行われた比較の数は、依然として通常のQuick-で行われた比較の数よりも非常に少ないですソート。
- 変更されたクイックソートの経過時間は、すべてのデータの通常のクイックソートの経過時間よりも非常に短いです。
すでにソートされたデータの時間複雑度O(n^2)が改善されたことを、どのように証明できますか？私は上記のデータをすべて持っていますが、理論的にどのように表示するのか分かりません。直接の回答はありませんが、ヒントは問題ありません。
小さな秘密：
この種の分析のための良いモデルは、彼のTimsortアルゴリズムのティム・ピーターの書き込みアップです。 「あなたの」改善はすでに何年も前に発見されています。 –
私は知っています。しかし、どこからでも概念をコピーするのではなく、私自身で実装する必要がありました。 – user1031752
@AurelioDeRosa私は、Robert Sedgewickのキャリアがこれらの改良によって開始されたと思います。 「Quicksortプログラムの分析」、Acta Informatica 7、1977を参照。 –