Asymptotische Komplexität der Sortierung mit k-Vergleichen

8

Das Sortieren unter Verwendung von 2-Element-Vergleichen hat eine asymptotische Worst-Case-Komplexität von (erreicht durch Mergesort, Heapsort, binäre Einfügung, mindestens Ford-Johnson), was optimal ist.nlog2(n)

Wenn wir mit Vergleichen sortieren, die k Elemente als Bausteine ​​sortieren, ist die informationstheoretische Untergrenze . Wir können leicht n log k ( n ) mit k-ary Insertion erreichen.nlogk!(n)nlogk(n)

Frage: Wo ist die optimale Komplexität zwischen und n log k ! ( n ) ?nlogk(n)nlogk!(n)

Geeignete Refs wären ebenfalls willkommen.

Edit: weil es nicht klar war:

Ich interessiere mich für die Komplexität in mit k = O ( 1 ) . Es hat das asymptotische Verhalten von α n log 2 ( n ) mit α [ 1nk=O(1)αnlog2(n), und ich möchte mehr Genauigkeit überα.α[1log2(k),1log2(k!)]α

slan_21
quelle

Antworten:

2

Lassen Sie uns diese zunächst in die meiner Meinung nach richtige Form bringen.


Θ(nlogk(n))=Θ(nlog2(n)log2(k))=Θ(nlog2(n)log2(k))

und

Θ(nlogk!(n))=Θ(nlog2(n)log2(k!))=Θ(nlog2(n)klog2(k))



Beachten Sie, dass ein -ary-Vergleich für ausreichtkk2 gleichzeitige (binäre) Vergleiche.

Zum 2k, k2Θ(k).

Durch das AKS-Netzwerk , z2kO(n), O(nlog2(n)k) k

Wann nk, 1k 1O(nlog2(n)k)

Daher für 2k, O(nlog2(n)k) k


5 k(4k2) Vergleich.

Zum 4k, 5k(32k) Vergleich.

Zum 2kn, log32(nk)=log2(nk)log2(32).

Zum 2kn, 5log2(nk)log2(32) k

Zum 2n, k

Daher für 2kn und nkO(1), Θ(1) k


Ich vermute, man könnte die zweite meiner beiden
Schlussfolgerungen verfeinern , um zu zeigen, dass Ihre Untergrenze erreicht ist.


quelle
nk=O(1)αnlog2(n)α[1log2(k),1log2(k!)]α5log2(nk)log2(32)=O((nk)log2(5)log2(32))
Ich wollte es so interpretieren, bevor mir klar wurde, dass, soweit ich finden kann, Die optimale Konstante ist selbst für nicht bekannt k=2.
2 Ist die optimale Anzahl von binären Vergleichen geteilt durch nlog2(n)1
k=2nlog2(n)i=2nlog2(i)nlog2(n)