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)

Ist jetzt die Fragestellung:

• Gib es einen Algorithmus mit O(c*n), mit dem man prüfen kann, ob alle Zahlen von 0 bis n-1 vorhanden sind?
  
• Muss man diese Aufgabenstellung implementieren z.B. Pseudocode?
  
• Ist zu zeigen, dass es diesen Algorithmus gibt, d.h. ein allgemein gültigen Beweis zu führen bzw. ihn zu widerlegen?
  

• Nein es soll die Fehlende Zahl im Array ermittelt werden, in O(n).
  
• Ja der Algorithmus soll in Pseudocode implementiert werden.
  
• Nein es ist nichts zu beweisen.
  

Ich glaub er meinte nicht das man die Bits umkopiert, sondern sich lediglich jeweils die Positionen der gerade/ungerade werte "merkt".

Dennoch bin ich der Meinung das dieser Algorithmus nicht die Komplexität O(n) hat, denn du wiederholst ja die Schritte (log n)-Mal. Also wäre es doch wieder O(n log n). Bitte korrigiert mich falls ich falsch liege!

Dies scheitert schon am dynamischen erstellen der Arrays nach jedem Durchgang.

Um die Werte zu summieren, müsstest man einmal jedes Element durchgehen => O(n) und die einzelnen Bits jedes Elements 0 => O(log n). Das ergibt dann eine Komplexität von O(n log n), wie Klotzkopp schon erwähnt hat.

Ja ich würde annehmen, dass die Bits in Abhängigkeit von n beschränkt sind. Denn ln(n)/ln(2) aufgerundet ergibt ja die Anzahl der Bits die benötigt werden um n als Dualzahl darzustellen.

Gesucht ist jedoch leider ein Algorithmus, welcher dies in O(n) erledigt

1, 2, 3, 4, 7, 8, 9

Oder fehlt immer nur eine Zahl?

Ja es fehlt immer nur eine Zahl.

Die Gesamtzahl der gesetzten Bits an Stelle k für alle Zahlen von 0 bis n steht fest. Wenn du dein Array nachzählst, und deine Summe für ein bestimmtes Bit um 1 zu klein ist, ist dieses Bit bei der fehlenden Zahl gesetzt.

Das würde doch bedeuten das ich für jedes Element einmal alle Bits durchgehen muss. Dies würde jedoch einen Aufwand von O(n²) haben, oder hab ich jetzt was falsch verstanden?

Hatte vergessen dazu zu schreiben, dass es sich um ein unsortietes Array handelt.

Hallo,

Gegeben ist ein Array[0..n-1], welches ganze Zahlen zw. 0 und n enthält. In diesem Array soll jetzt die fehlende Zahl x mit 0<= x <= n in O(n) ermittelt werden. Das schwierige ist jedoch das man nur auf das k-te Bit des i-ten Elements in kostanter Zeit zugreifen kann. Also ein Zugriff nur mittels A[k] zur Verfügung steht.

Mein Gedankengang war erstmal, das man überprüft ob eine gerade od. ungerade Zahl fehlt, welches ja anhand des ersten Bits leicht geprüft werden kann. Somit hätte man ja schon die hälfte der Möglichkeiten eliminiert. Jedoch hab ich noch keine Idee, wie ich jetzt weiter verfahren soll.

Hoffe mein Anliegen ist verständlich und ihr habt ein paar Ideen dazu