Die Mathe-Redaktion [Home] - Neues auf einen Blick 03.10.2023 19:34 [Neues] [Forum] [Suche] - Registrieren/Login
 
Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Arrays mit Initialisierung in O(1)
Autor
Universität/Hochschule Arrays mit Initialisierung in O(1)
4ndre4s
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2022
Mitteilungen: 1
  Themenstart: 2022-06-01

Hey, ich soll eine Datenstruktur auf Basis von Arrays entwerfen. Diese soll sich wie ein Array verhalten, dessen Einträge zuerst mit 0 initialisiert wurden, sich im Gegensatz dazu jedoch in O(1) initialisieren lässt. Die Datenstruktur muss für ein N fest aber beliebig Platz für N ganze Zahlen bieten, Das Auslesen und das Verändern einer beliebigen Stelle i mit 0<= i <= N in Zeit in O(1) ermöglichen Beim Auslesen einer Stelle i, der noch kein Wert zugewiesen wurde, 0 zurückgeben Dabei O(N) Speicher benötigen, aber in Zeit in O(1) initialisiert werden können Mein Problem hierbei ist, dass ich nicht verstehe wie eine solche Datenstruktur aussehen soll bzw. wie sie funktioniert, da Arrays ja für gewöhnlich in O(n) initialisiert werden.

   Profil
Folgende Antworten hat der Fragensteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
darkhelmet
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 05.03.2007
Mitteilungen: 2685
Wohnort: Bayern
  Beitrag No.1, eingetragen 2022-06-02

Hi, ja genau, wenn du die Nullen tatsächlich in das Array schreibst, wird das immer O(N) sein, daran kannst du nichts ändern. Statt dessen musst du dir merken, welche Stellen noch nicht überschrieben wurden. Und diese Information musst du in O(1) beschaffen können, damit du beim Auslesen ggf. den Arraywert durch eine 0 ersetzen kannst. Mit zusätzlichem Speicher kannst du relativ großzügig sein. 2N oder 3N ist ja immer noch O(N). Wenn du kein Genie bist, wirst du dir nicht direkt die Lösung aus dem Hut ziehen können. Im Normalfall kommt man erst drauf, wenn man ein paar naive Ansätze probiert hat und verstanden hat, warum sie nicht funktionieren.

   Profil
4ndre4s wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]