ethrandil
2006-11-09, 20:00:28
Hallo,
wie hinreichend bekannt ist, gibt es Linked und Array-Listen mit unterschiedlichen Komplexitäten für die Listenoperationen.
Ich dachte aber, dass man das auch mit verketteten Arrays machen kann und habe berechnet, dass man wenn man im Schnitt immer eine Arraygröße von sqrt(n) hat, auch viele Optionen in O(sqrt(n)) realisierbar sind. (Nur search nicht.)
Gibt es dazu auch was zu lesen? Dann muss ich nicht das Rad neu erforschen... Oder ist meine Idee aus anderen Gründen Humbug oder irrelevant?
mfg
- eth
http://www.cs.toronto.edu/~gfb/csc148/2003F/a2/
wie hinreichend bekannt ist, gibt es Linked und Array-Listen mit unterschiedlichen Komplexitäten für die Listenoperationen.
Ich dachte aber, dass man das auch mit verketteten Arrays machen kann und habe berechnet, dass man wenn man im Schnitt immer eine Arraygröße von sqrt(n) hat, auch viele Optionen in O(sqrt(n)) realisierbar sind. (Nur search nicht.)
Gibt es dazu auch was zu lesen? Dann muss ich nicht das Rad neu erforschen... Oder ist meine Idee aus anderen Gründen Humbug oder irrelevant?
mfg
- eth
http://www.cs.toronto.edu/~gfb/csc148/2003F/a2/