Finden der fehlenden Zahl in einem Array

[smoon]

Ja das ist Korrekt, dass bei jedem Vergleich weniger Daten durchgegangen werden (das ist das was du berechnet hast), aber du musst das noch mit der Anzahl der durchgeführten Vergleiche multiplizieren und dann ist es nicht mehr O(n)

[Jan Jansen]

Rechne mir das bitte mal an einem Beispiel vor

[TheFinn]

Bitte gebt mir eins auf den Deckel, wenn ich jetzt kompletten Unfug erzähle, aber ist das nicht eine Paritätsberechnung?

Ich verteile n Bitfolgen der Breite c auf n Platten eines RAID-Arrays (4 oder 5, 'passende' Blockgrößen vorausgesetzt) mit n Nutzplatten und einer Parity-Platte. Dann fällt mir eine der Platten aus und ich mache ein XOR über alle anderen, um die verlorenen Bits zu rekonstruieren. Läuft das nicht in O(c*n) ?

[Klotzkopp]

Läuft das nicht in O(c*n) ?

Doch, aber c ist nicht konstant. Du brauchst ja mindestens c = log2(n) Bits, um die Werte darstellen zu können.

[Panke]

Die Anzahl der Bits ist aber bereits berücksichtigt. Die Anzahl der Bits entspricht der maximalen Anzahl der Summanden. Aber egal wie viele das werden, es bleibt bei O(n), da die Reihe nun mal entsprechend konvergiert.