셸 정렬에 대한 최악의 시나리오 : Θ (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"가 하나만있는 것처럼 보이지만, 갭 시퀀스이라는 매개 변수로 매개 변수화 된 정렬 기능 패밀리가있는 것처럼 보입니다. Shellsort는 h의 값을 줄이기 위해 여러 번 목록을 h- 정렬하여 작동합니다. h의 순서는 Shellsort의 수행 방법을 결정합니다. 일부 시퀀스는 O (N^3/2)을 제공하고 일부는 O (N^2)를 제공하고 다른 시퀀스는 O (N 로그^2 N)을 제공합니다.

확률은 각각 다른 참조 그들의 점근선 범위를 유도했다.

편집 : 가능한 최악의 간격 순서 (반복 없음)를 고려하십시오 n, n-1, n-2, ..., 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 될 것입니다 삼). 이것은 가능한 최대의 복잡성이 갭 시퀀스를 엄격하게 감소시키는 갭 (엄격하게 감소하지 않는 갭 시퀀스는 임의로 나쁠 수 있기 때문에 흥미롭지 않습니다)에 대해 생각할 것입니다.