Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:aud:loesungss11 [21.03.2018 11:58] – Evren | pruefungen:bachelor:aud:loesungss11 [20.06.2020 12:12] (aktuell) – BierBaron69 | ||
---|---|---|---|
Zeile 37: | Zeile 37: | ||
Ein erster Eintrag von Element x lässt sich in einer sortierten Reihung mittels binärer Suche in O(log n) finden. \\ | Ein erster Eintrag von Element x lässt sich in einer sortierten Reihung mittels binärer Suche in O(log n) finden. \\ | ||
Um zu prüfen, ob (wie viele ist irrelevant!) es noch weitere Einträge von Element x gibt, muss man nur das Element rechts und links vom aktuellen betrachtet, was in O(1) geht. | Um zu prüfen, ob (wie viele ist irrelevant!) es noch weitere Einträge von Element x gibt, muss man nur das Element rechts und links vom aktuellen betrachtet, was in O(1) geht. | ||
+ | |||
+ | Anmerkung: | ||
+ | Es geht ja um den worst case. Ich denke, man kann ein Szenario konstruieren, | ||
**i)** 2. Antwort ist richtig | **i)** 2. Antwort ist richtig | ||
Zeile 489: | Zeile 492: | ||
(I ∧ b): | (I ∧ b): | ||
p = 2^(n - k - 1) ∧ k ≥ 0 ∧ k > 0 | p = 2^(n - k - 1) ∧ k ≥ 0 ∧ k > 0 | ||
- | <=> p = 2^(n - k - 1) ∧ k > 0 (weil: (k ≥ 0 ∧ k > 0 <=> k > 0)) | + | <=> p = 2^(n - k - 1) ∧ k > 0 (weil: (k ≥ 0 ∧ k > 0) < |
wp(B, I): | wp(B, I): |