Mit Eingängen x 0 , … , x n - 1 bauen wir ein zufälliges Sortiernetz mit m Gattern auf, indem wir iterativ zwei Variablen x i , x j mit i < j auswählen und ein Komparatorgatter hinzufügen, das sie vertauscht, wenn x i > x j .
Frage 1 : Für feste , wie groß muss m für das Netzwerk mit Wahrscheinlichkeit richtig sortieren sein > 1 ?
Wir haben mindestens die untere Schranke seit einer Eingabe , die korrekt mit Ausnahme sortiert ist , dass jedes aufeinanderfolgende Paar ausgelagert wird , nehmen Θ ( n 2 log n 2 ) Zeit für jedes Paar als Komparator gewählt werden , . Ist das auch die Obergrenze, möglicherweise mit mehr log n Faktoren?
Frage 2 : Gibt es eine Verteilung von Komparatorgattern, die ergibt, möglicherweise durch Auswahl enger Komparatoren mit höherer Wahrscheinlichkeit?
quelle
Antworten:
Hier sind einige empirische Daten zu Frage 2, die auf der Idee der DW für die bitonische Sortierung basieren. Wählen Sie für Variablen j - i = 2 k mit einer Wahrscheinlichkeit proportional zu lg n - k und wählen Sie dann i gleichmäßig zufällig, um einen Komparator ( i , j ) zu erhalten . Dies stimmt mit der Verteilung von Komparatoren in bitonischer Sortierung überein, wenn n eine Potenz von 2 ist, und approximiert sie ansonsten.n j−i=2k lgn−k i (i,j) n
To emphasize: I'm using only6400 bit sequences to approximate the expected number of gates, not 2n . The mean required gates does rise with that number: for n=199 if I use 6400 , 64000 , and 640000 sequences the estimates are 14270±1069 , 14353±1013 , and 14539±965 . Thus, it's possible getting the last few sequences increases the asymptotic complexity, though intuitively it feels unlikely.
Edit: Here's a similar plot up ton=80 , but using the exact number of gates (computed via a combination of sampling and Z3). I've switched from power of two d=j−i to arbitrary d∈[1,n2] with probability proportional to logn−logdd . Θ(nlog2n) still looks plausible.
quelle