Algorithmen und Datenstrukturen · Senior · Frage 71 von 75
Was beantwortet die Struktur „Sparse Table“ in O(1)?
- 1Bereichsminimum-Abfragen auf einem statischen Array
- 2Prüfungen auf Enthaltensein in einer dynamischen Menge
- 3Kürzeste Wege zwischen zwei beliebigen Knoten
Antwort zeigen
Richtige Antwort: Bereichsminimum-Abfragen auf einem statischen Array
Erklärung
Sie berechnet in O(n log n) die Minima aller Bereiche der Länge 2ᵏ vor. Jeder Bereich wird von zwei überlappenden Zweierpotenz-Bereichen abgedeckt, und dem Minimum ist die Überlappung egal. Updates würden einen Neuaufbau erfordern.