Gegeben ein Array, finde top 'x' in O (1)

Question

Ich werde das Problem schreiben, wie ich es gefunden habe und ich werde dann erklären, was mich verwirrt.

"Ein Lehrer markiert die Arbeit seiner Schüler von 0-10, aber er markiert nur mit einer 8 oder darüber für eine bestimmte Zahl" x "(x = 15) der" n "Schüler ein Array mit allen Schülern in zufälliger Reihenfolge. Finde die 'x' besten Noten in O (1). "

Wir haben sicherlich gelernt Hashing, aber das erfordert mich alle Daten in einer Hash-Tabelle zu speichern, die definitiv nicht O (1) ist. Vielleicht müssen wir die "Umwandlung" nicht berücksichtigen? Wenn wir das tun, wird die Umrechnung, kombiniert mit der Suchzeit danach, zu einer anderen Methode als Hashing führen.

In diesem Fall, abgesehen von O (1), was ist der schnellste Algorithmus einschließlich der Umwandlung und der Suchzeit?

Answer 1

Einfach: Es ist nicht möglich.

O(1) kann nur erreicht werden, wenn die gesamte Eingabegröße, die Anzahl der erforderlichen Vergleiche und die Ausgabegröße Konstanten sind. Sie können argumentieren, dass x als Konstante behandelt werden könnte, aber es immer noch nicht funktioniert:

Sie müssen nicht jedes einzelne Eingabeelement prüfen, alle n von ihnen, wie die zufällige Eingabereihenfolge nicht einmal irgendwelche Heuristik erlauben zu erraten wo das x ten Element wäre, auch wenn Sie bereits die anderen x-1 Elemente bereits in konstanter Zeit richtig erraten hätten.

Da das Problem angegeben ist, gibt es keine Lösung, die es in den oberen Grenzen von O(1) oder O(x) tun kann.

---

Nehmen wir an, nur Ihr Lehrer seinen Fehler korrigiert, und gibt Ihnen eine überarbeitete Version, die O(n) korrekt besagt als die obere Grenze erforderlich.

In diesem Fall ist Ihr Hash-Ansatz (fast) korrekt. Der Haken bei der Verwendung einer Hash-Funktion besteht darin, dass Sie nun potenzielle Kollisionen auf der Hash-Funktion berücksichtigen müssen, weshalb Hash-Maps nicht streng in O(1) funktionieren, sondern nur "im Durchschnitt" in O(1).

Da Sie alle möglichen Werte kennen (Noten von 0-10), können Sie Buckets nur mit einem bekannten Index zuordnen. Innerhalb jedes Buckets können Sie verknüpfte Listen verwenden, da sie auch konstante Zeiteinfügungen und lineare Zeit-Iterationen ermöglichen.