Algorithmen und Datenstrukturen · Middle · Frage 73 von 75
Was kostet es, einen Wert in ein sortiertes Array einzufügen und es sortiert zu halten?
- 1O(n): die Stelle zu finden ist O(log n), das Verschieben aber O(n)
- 2O(1): JavaScript-Arrays können überall gratis einfügen
- 3O(log n): binäre Suche findet die Position direkt
Antwort zeigen
Richtige Antwort: O(n): die Stelle zu finden ist O(log n), das Verschieben aber O(n)
Erklärung
Binäre Suche findet die Position schnell, aber splice bewegt trotzdem jedes spätere Element. Für viele Einfügungen mit Abfragen dazwischen passt ein balancierter Baum oder ein Heap (je nach Abfragen) besser.