Algorithmen und Datenstrukturen · Senior · Frage 61 von 75
Was ist die untere Schranke für das Finden eines Elements in einem unsortierten Array, und warum?
- 1Ω(log n): mit geschicktem Probieren kann man halbieren
- 2Ω(1): Hashing findet es sofort
- 3Ω(n): jede ungeprüfte Position könnte das Ziel enthalten
Antwort zeigen
Richtige Antwort: Ω(n): jede ungeprüfte Position könnte das Ziel enthalten
Erklärung
Ein Gegenspieler-Argument: überspringt ein Algorithmus eine Position, könnte das Ziel dort liegen. Hashing hilft erst nach einem O(n)-Vorverarbeitungsschritt, der die Tabelle baut.