Autor Beitrag
Spaceguide
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 552


(D3/D7/D8) Prof.
BeitragVerfasst: So 30.10.05 14:36 
Ist TList.Items[] eher O(1), O(log n) oder O(n)?
UC-Chewie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 531

WinXP
D5 Ent
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 552


(D3/D7/D8) Prof.
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 552


(D3/D7/D8) Prof.
BeitragVerfasst: So 30.10.05 16:00 
Ich muss mir mal die Sources angucken, müsste in classes.pas zu finden sein.
UC-Chewie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 531

WinXP
D5 Ent
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 552


(D3/D7/D8) Prof.
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: 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:

ausblenden 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 user profile iconUGrohne: Code- durch Delphi-Tags ersetzt

_________________
wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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.