Das Finden der höchsten 2 Zahlen- Informatik

Question

Ich versuche, einen Algorithmus, um herauszufinden, die höchsten zwei Zahlen in einer Liste von Zahlen zu finden.

Die höchste Zahl kann in n-1 Stufe gefunden werden, vielleicht durch die Faust Schritt einer Blase Art oder etwas in diese Richtung zu tun. Mir scheint es, dass die nächst höhere Zahl zu finden, könnte auch in insgesamt 1,5 N Vergleiche im Durchschnitt zu finden.

Mein Professor hat uns Hausaufgaben ein alogrithm zu schreiben, die die höchsten 2 Zahlen in n + log (n) Vergleiche findet. Ist das überhaupt möglich? Irgendwelche Ideen, Anregungen?

Edit: Wenn ich sage, n + log (n) ich bin nicht auf O (n + log n), sondern genau n + log n

Answer 1

Ja, es ist möglich, sie in nicht mehr tun, als (n + log n). Ich kann wirklich nicht sagen, wie, ohne die Antwort zu geben weg, aber lassen Sie mich versuchen. :-)

Nehmen Sie die n Zahlen, vergleichen sie zu einer Zeit zu zweit. Nehmen Sie die ceil (n / 2) „Gewinner“ und wiederholen „wie ein binärer Baum“. Fragen: Wie viele Vergleiche braucht es, um das größte zu finden? Wie viele Menschen ist diese „Gewinner“ gewinnen gegen? Wem könnte die zweitgrößte verloren haben? So wie viele Vergleiche dauert es nun die zweitgrößte Zahl zu finden?

Die Antwort stellt sich heraus, insgesamt sein, n-1 + Decke (n log) - 1 Vergleiche, wo das Protokoll zur Basis 2 ist Sie auch mit einem kontradiktorischen Argument nachweisen kann, dass es nicht möglich ist, als dies im schlimmsten Fall besser zu machen.

Answer 2

Edit: Ups, eine einfache Sache verpasst wegen Dummheit. Diese Lösung ist nicht richtig, obwohl ich es bin hier zu halten, wie es noch avg (n + log (n)). Dank ShreevatsaR für meine Dummheit Hinweis. Ich habe die Baumsuche betrachten, verpasste aber komplett die Idee der Rückzieher die zweithöchste Zahl in log (n) zu finden.

Wie auch immer, hier folgt mein Beweis dafür, warum der untere Algorithmus ist nicht mehr als avg (n + log (n)). Im wirklichen Leben sollte es führt immer noch ziemlich gut zumindest.

• Erste vergleichen gegen die zweithöchste Zahl aufgezeichnet.
• Nur wenn dieser Vergleich erfolgreich ist, zu vergleichen, gegen die höchste aufgezeichnete Zahl.

Um zu beweisen, dass es im Durchschnitt n + log n ist, müssen wir einfach beweisen, dass der erste Vergleich ist nur erfolgreich, log (n) mal im Durchschnitt. Und das ist ziemlich einfach zu sehen oder zu demonstrieren.

1. Nehmen wir P als der Ist-Position des aktuellen zweitgrößte Zahl in einer sortierten Version der Liste, und führen Sie den Algorithmus
2. Wenn P> 2 dann, wenn eine größere Zahl gefunden wird, wird die neuen P im Durchschnitt nicht mehr als P / 2.
3. Wenn P = 2, dann der erste Vergleich nicht erfolgreich sein kann, da es keine Zahl, die größer als die aktuellen zweitgrößte Zahl ist.
4. P kann höchstens gleich N
5. 2, 3 und 4 sollte es trivial sein, zu sehen, dass der erste Vergleich nicht mehr als log (N) mal im Durchschnitt erfolgreich sein kann.

Answer 3

Wie wäre es damit:

for each listOfNumbers as number
    if number > secondHighest
        if number > highest
            secondHighest = highest
            highest = number
        else
            secondHighest = number

Answer 4

Die Antwort von ShreevatsaR geschrieben scheint O (n log n) zu sein.

Der erste Durchgang (n Operationen) erzeugt n / 2 Antworten. Durch Wiederholung, ich denke, du meinst du wirst n / 2 Operationen tun, um n / 4 Antworten zu erzeugen. Sie werden die Schleife log n mal durchlaufen. Dies ist ein viel wie ein Mergesort, außer dass Mergesort immer verarbeitet n jedes Mal durch die Knoten. Außerdem wird die Schleife log n-mal. Und ich sehe nicht, wie diese Algorithmus Spur der zweiten higest Zahl halten wird.

Nickf hat die richtige Antwort. schlimmster Fall ist, wenn die Liste sortiert ist, wird es 2n Vergleiche tun -., dass O (n)

ist

btw, O (n + log n) O (n) die Bestellbezeichnung zu schlimmsten Fall asymptotisch Wachstum bezieht.

Answer 5

Sie können mit Countingsort, Radixsort, Bucketsort oder anderem linearen Algorithmus zuerst die Liste sortieren, in absteigender Reihenfolge. Dann bekommen nur die ersten 2 Elemente der sortierten Liste. So wird dies (n) + 2 = (n)

Beachten Sie, dass diese Algorithmen in linearer Zeit sortieren, weil jeder seine eigenen Annahmen hat.

Answer 6

Pseudocode (ist das nicht im Wesentlichen n?)

int highestNum = 0
int secondHighest = highestNum

for(i = 0; i < list.length; i++)
{
if(list[i] >= highestNum)
{
secondHighest = highestNum
highestNum = list[i]
}
}