Wie viele binäre Suchen müssen in einer Tabelle n-element ausgeführt werden, um die Vorbereitungszeit zurückzukaufen, die zum Sortieren der Tabelle erforderlich ist?Wann muss ich die binäre Suche anstelle der linearen Suche verwenden?
Es ist eine knifflige Frage, denn es hängt vom Algorithmus ab, den Sie zum Sortieren verwenden, Details zur binären Implementierung der Suche und so weiter.
Ohne Kenntnis von spezifischen Implementierungen können wir Analyse nur in Bezug auf die Big-O-Notation beginnen (aber es ist nicht genau, wie die Komplexität für Algorithmus O (2n) gleich O (n), sondern nehmen etwa zwei mal mehr)
Analyse
Binary search = O(logn)
Sorting = O(nlogn)
Linear search = O(n)
Sie benötigen K Suchen durchführen. Also für den rohen unsortierten Array a[n] für unterschiedliche Suchanfragen benötigen Sie
Binary Search
Suche k mal
TOTAL (BS) = O (log n) + k * O (logn)
Linear Suchen
Suche nur k mal
TOTAL (LS) = k * O (n)
Nun versuchen die Gleichung zu lösen, durch k zu vergleichen und n
nlogn + klogn < kn
log(n^n) + log(n^k) < kn
log(n^(n+k)) < kn
n^(n+k) < 2^kn
2^kn - n^(n+k) > 0
(Ich bin nicht Mathematiker, ist dies als einfachste wie ich bekommen kann)
Wenn Sie nun Eingang für Ihren Algorithmen N und K haben, bewerten gerade letzten Ausdruck zu finden, mindestens K mit binärer Suche zu gewinnen.
Beispiel
sei angenommen, n = 1000
2^(1000k) - 1000^(1000 + k)> 0
Dieser Ausdruck gilt, wenn K> 10, Für n = 10000, Ausdruck gilt, wenn k> 9
Schlussfolgerung
Wenn Ihr Array größer als 1000 Elemente ist, müssen Sie mindestens 10 Binärsuchen ausführen, um die Investition zurück zu senden
Die numerischen Ergebnisse stehen nur unter der Annahme, dass alle in der großen O-Notation versteckten konstanten Faktoren 1 sind. – Henry
Ihre andere "Schlussfolgerung" sollte sein, dass, wenn "n" zunimmt, "k" abnimmt. Das heißt, je größer das Array, desto weniger Suchvorgänge benötigen Sie, um die zum Sortieren benötigte Zeit wiederzuerlangen. Weil 'k * n 'schneller zunimmt als' (n + k) * log (n) '. –
Binäre Suche wird verwendet, wenn Daten in sortierter Reihenfolge vorliegen. Die binäre Suche gibt Ihnen die Leistung von O (logn). Wenn Sie mehr Suchen als Einfügungen haben, wird die binäre Suche eine verbesserte Leistung liefern. wo als lineare Suche ist O (n). Die lineare Suche kann verwendet werden, wenn Daten nicht geordnet sind.
Sie sprechen absolute Zeit - wie in Sekunden und Millisekunden? –
Das hängt von den Implementierungsdetails ab und kann nur experimentell herausgefunden werden. – Henry
Was denkst du? –