Schnellste Weg, um Art 3 Werte in Java
Ich muss 3 Werte in der richtigen Reihenfolge, und drucken Sie Sie aus der Konsole.
Lösung ist, um Sie in ein array und Sortieren Sie dann, aber ich erinnere mich (noch aus Schulzeiten), dass es schneller zu vergleichen und bestellen Sie diese, aber ich kann nicht finden, die richtige Vergleich, um.
Könnten Sie mir bitte zeigen, wie zu vergleichen, die 3 Werte mit der minimalen Anzahl von if
Aussagen?
- Für drei Gegenstände bubble-sort wäre genau richtig.
- Für die drei Elemente bogosort würde das gut machen.
- Verwandte: Schnellste Art von fester Länge ist 6 int-array
Du musst angemeldet sein, um einen Kommentar abzugeben.
Gibt es keinen Punkt in der Optimierung dieser. Es wird nicht an jeder Geschwindigkeit. O(n!) für 3 ist nur noch 3*2 = 6 Operationen. Sogar O(2^n) ist 8. Sie könnte wirklich zu tun, was es braucht, zu Sortieren, diese 3 Werte und nicht sehen, einen Unterschied in der Leistung.
Bearbeiten
if( b > c ){ max = b; min = c; }else{
Denn sobald a größer ist als b, aber a ist nicht größer als c, dann ist b nie größer als c ist.bubble-sort hätte nur 3 vergleichen ops und 6 Zuweisungen im schlechtesten Fall (es wird sehr ähnlich, wenn nicht identisch zu dem Verhalten von insertion sort in diesem Fall):
Es nicht getan werden kann in weniger als 3 vergleicht, weil es
n!=6
möglichen Permutationen für das array, undceil(log_2(n!)) = 3
breaking out
- Optimierung). wennn==3
es Sie (3-1) + (2-1) = 2+ 1 = 3 vergleichen ops. Es ist kein Punkt, darüber zu reden big O beim Umgang mit den 3 Elementen.3
Elemente mit einer vernünftigen bubble-sort-Implementierung ist3
Vergleiche und2
swaps, nicht9
nichts. Die big-O-notation ist eine drastische Vereinfachung von dem, was in der Regel eine sehr viel komplizierter und schwieriger zu bestimmen, die genaue Formel für die Anzahl der Operationen; die Kosten für diese Vereinfachung ist, dass es erlaubt zu überschätzen, die zu verschiedenen Graden.f(x)
istO(g(x))
- dann gibt es x0,M, so dass für jedes x > x0:|f(x)| < M*g(x)
. Wenn x < x0 - sind alle Wetten ab. Wir können Ihnen nichts sagen. Zum Beispiel ist die Funktionf(x) = { if x < 10: x^10 | otherwise: x }
. Durch die definition von big O, wir Holenf(x)
istO(x)
. Das sagte - ich bin schlafen gehen, Arbeit morgen. Sie sind mehr als willkommen, um zu öffnen, einen chat und ich werde versuchen zu erarbeiten morgen - wenn Sie bereit sind zu lernen.a <= b <= c
odera > b > c
. Es kann nicht sein fertig in weniger als 2 vergleicht.Omega(nlogn)
problem, wenn klar kannst du sort sortiert ein array inO(n)
?Could you please show how to compare 3 values by minimium values of if()?
schlägt er muss wenigsten möglich, "wenn-Aussagen" (interpeted Vergleiche), und es soll für jeden Eingang. Ein worst-case-Komplexität Analyse ist eine sehr häufige implizite Annahme in der Literatur, und ich werde nicht darüber streiten, entweder es ist richtig oder nicht.ceil(log_2(3!)) > 2
, so dass nicht passieren wird). Guten Tag.a <= b
undc => b
dann brauchen Sie nicht zu vergleichena
zuc
. allerdings, wennb
ist nicht Mitte, dann haben Sie 3 Vergleiche.Soweit ich weiß, benutzt Java die Quicksort Algorithmus für die Sortierung einer bereits optimierten Ansatz. Keine Geschwindigkeit ernten Sie hier!