17. Mai 200817 j 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)
19. Mai 200817 j 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) ?
19. Mai 200817 j 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.
20. Mai 200817 j 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.
Archiv
Dieses Thema wurde archiviert und kann nicht mehr beantwortet werden.