シェルソートの最悪シナリオ：Θ（N^3/2）またはO（（NlogN）^ 2）？

Question

シェルソートの最悪のケースを探しています。 thisによれば、最悪の場合はO(N^3/2) であるが、hereであり、最悪の場合はO((N log N)^2))であると主張されている。

私は、最悪の場合は、奇数の位置に最も大きな値を含むシーケンスであると考えます。しかしながら、hereは、いくつかのギャップシーケンスがΘ(N^3/2)の複雑さで導入されている。

シェルソートの実際の最悪のケースは何かを突き止めようとしています。これまでのところ、上記の論文によれば、最悪の場合はO((N log N)^2))ではなく、Θ(N^3/2)です。さらに、hereは、最悪のシナリオ分析を示唆しました。明らかに、Θ(N^3/2)ではありません。

Hereの場合、最悪の場合はO(N^2)のアルゴリズムで時間複雑度分析が行われます。

しかし、私は完全に失われています。シェルソートの最悪のケースは何ですか？

Answer 1

「Shellsort」は1つではなく、ギャップシーケンスと呼ばれるものによってパラメータ化されたソート関数ファミリのようです。 Shellsortは、hの値を減らすためにリストを複数回h-sortingすることによって動作します。使用されるhのシーケンスは、Shellsortの実行方法を決定します。いくつかの配列はO（N^3/2）を与え、あるものはO（N^2）を与え、他のものはO（N log^2 N）を与えるものもあります。

Oddsは、彼らの漸近的な境界を導き出す。

編集：最悪のギャップシーケンス（繰り返しなし）を考慮してください。n,,、...、1ランタイムを取得するには：

h sublists sublist size comparisons 
n n  1 (n)   0 
n-1 n-1  1 (n-2), 2 (1) 1 
n-2 n-2  1 (n-4), 2 (2) 2 
... 
n/2 n/2  2 (n/2)   2n 
... 
n/3 n/3  3 (n/3)   3n 
... 
n/4 n/4  4 (n/4)   4n 
... 
n/n   n (1)   n^2 

をだから、答えは^ n個のようなもの（1 + 2 + ... + N）= N^2（N + 1）/ 2、またはO（n個になるだろう3）。これは、可能な限り複雑なギャップがギャップシーケンスを厳密に減少させることになると考えていることです（厳密に減少していないギャップシーケンスは、それらが任意に悪い可能性があるので面白くない）。