| Autor |
Beitrag |
Spaceguide
      
Beiträge: 552
(D3/D7/D8) Prof.
|
Verfasst: So 30.10.05 14:36
Ist TList.Items[] eher O(1), O(log n) oder O(n)?
|
|
UC-Chewie
      
Beiträge: 531
WinXP
D5 Ent
|
Verfasst: So 30.10.05 14:47
O(1). Oder einfacher gesagt: Es ist ein Array 
_________________ Egal wie dumm man selbst ist, es gibt immer andere, die noch dümmer sind
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: So 30.10.05 15:15
naja kommt drauf an was du damit machst
einfügen = O(1) suchen = O(n) bei sortiert suchen O(log n) beim sortieren O(n²) oder O(n log n) je nach alg
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
|
|
Spaceguide 
      
Beiträge: 552
(D3/D7/D8) Prof.
|
Verfasst: So 30.10.05 15:56
Also wenn es ein Array ist, dann geht Einfügen nicht in O(1), wenn es eine verkettete Liste ist, dann geht der Zugriff nicht in O(1).
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: So 30.10.05 15:59
Moment, ein array wirds denk ich mal nicht sein.
Ist jetzt noch die frage wo es eingefügt wird in einer Liste. d.h. Als oberstes oder als letzes Element. Wirds als letztes Element eingefügt dann dauert das Einfügen O(n) (da erst alle pointer durchgeganen werden müssen) Als 1. wird nur der Pointer auf erste Element umgeändert.
Beim Zugriff stimmts so wie es Spaceguide gesagt hat, nur das es beim array O(1) wäre und wie gesagt in einer Liste O(n)
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
|
|
Spaceguide 
      
Beiträge: 552
(D3/D7/D8) Prof.
|
Verfasst: So 30.10.05 16:00
Ich muss mir mal die Sources angucken, müsste in classes.pas zu finden sein.
|
|
UC-Chewie
      
Beiträge: 531
WinXP
D5 Ent
|
Verfasst: So 30.10.05 16:20
Es ist definitv ein Array, ich hab mir schon mal die Sourcen angekuckt.
Aber OK, O(1) ist es halt nur beim Zugriff.
_________________ Egal wie dumm man selbst ist, es gibt immer andere, die noch dümmer sind
|
|
Spaceguide 
      
Beiträge: 552
(D3/D7/D8) Prof.
|
Verfasst: So 30.10.05 18:38
Hmm, also da TList.Add ein Grow auslösen kann, welches zu einem ReallocMem führt, ist Add definitiv O(n)!
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: So 30.10.05 19:00
also da es ein Array ist ist der zugriff schon mal O(1)
aber durch ein ReallocMem kann man nicht sagen, dass man O(n) hat, da z.b. viel mehr Speicher am Anfang allokiert wird, und erst wenn der voll ist, nochmal etwas dazukommt
etwa so:
Delphi-Quelltext 1: 2: 3: 4:
| var x = 0; procedure ReallocMem; if frei+needed > maxmem then maxmem := VirtuaAlloc( maxmem+$1000 bytes) |
d.h. es wird immer mehr speicher allokiert als benötigt und somit nich wirklich bei jedem ReAllocMem der speicher auch neu allokiert
aber da weiß ich leider nicht wie der MemoryManager das macht
Moderiert von UGrohne: Code- durch Delphi-Tags ersetzt
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: So 30.10.05 21:43
Der Speichermanager von Delphi ist im Bereich O(n) bis (On log n). Der basiert auf verketteten Listen und Block-Subdivides. Ich bin mir aber grad nicht sicher, inwiefern im Extremfall ein O(n^2) auftreten kann.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|