Article View: be.comp.programming
Article #6733tijdscomplexiteit : sorteren in een cirkel
From: Dieter D'Hoker
Date: Thu, 21 Nov 2002 21:14
Date: Thu, 21 Nov 2002 21:14
39 lines
2474 bytes
2474 bytes
stel je hebt een cirkel van n - personen , en je wilt die rangschikken volgen geboortedatum , gewicht , lengte , je kiest maar ... elke persoon mag de cirkel niet verlaten , en per plaats in de cirkel mag er maar juist 1 persoon staan ... Wat is de beste methode om deze cirkel te sorteren ... mogelijkheden : a) elke persoon vergelijkt met zijn buurman links van hem als ie hoger is doet hij niks , als hij lager is dan verwisselen ze van plaats ... b) Men zoekt de laagste waarde tussen de personen , dit is de beginpersoon ... Dan zoekt men telkens de persoon die daar op volgt , en die vcerplaatst zich dan ... Welke systeem heeft de hoogste tijdscomplexiteit ? Stel dat de verplaatsing van 1 plaatsje in de cirkel als tijdscomplexiteit 1 heeft . En de vergelijking van 1 waarde van een persoon met de waarde van een andere persoon ook tijdscomplexiteit 1 heeft . Iemand een idee ? En een formule in functie van n (n = aantal personen = aantal plaatsen in de cirkel) om dit te onderbouwen ? -- Dieter D'Hoker http://dieter.dhoker.com/ news:free.nl.dieter.dhoker & news:alt.nl.fan.dieter.dhoker
Technical Details
Message-ID:
<3ddd4ca5$0$46603$e4fe514c@news.xs4all.nl>Path:
arc1-ca.pugleaf.net!archiver1.google.com!news1.google.com!sn-xit-02!sn-xit-05!sn-xit-01!sn-xit-08!supernews.com!38.144.126.76.MISMATCH!feed2.newsreader.com!newsreader.com!news.telebyte.nl!newshub1.home.nl!home.nl!news2.euro.net!transit.news.xs4all.nl!news.xs4all.nl!not-for-mailShow Full Headers
Complete Article Headers
X-Google-Language: DUTCH,ASCII-7-bit X-Google-Thread: 107324,46214dff648db5b1,start X-Google-Attributes: gid107324,public X-Google-Thread: f5500,46214dff648db5b1,start X-Google-Attributes: gidf5500,public X-Google-Thread: fcea4,46214dff648db5b1,start X-Google-Attributes: gidfcea4,public X-Google-Thread: f7e01,46214dff648db5b1,start X-Google-Attributes: gidf7e01,public X-Google-ArrivalTime: 2002-11-21 13:14:54 PST Path: arc1-ca.pugleaf.net!archiver1.google.com!news1.google.com!sn-xit-02!sn-xit-05!sn-xit-01!sn-xit-08!supernews.com!38.144.126.76.MISMATCH!feed2.newsreader.com!newsreader.com!news.telebyte.nl!newshub1.home.nl!home.nl!news2.euro.net!transit.news.xs4all.nl!news.xs4all.nl!not-for-mail From: "Dieter D'Hoker" <webmaster@neverseenbefore.com> Newsgroups: be.comp.programming,be.science,nl.comp.programmeren,nl.wetenschap Subject: tijdscomplexiteit : sorteren in een cirkel Date: Thu, 21 Nov 2002 22:14:02 +0100 Organization: dieter.dhoker.com (post does not reflect views of Dieter D'Hoker) X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2800.1106 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106 Lines: 41 Message-ID: <3ddd4ca5$0$46603$e4fe514c@news.xs4all.nl> NNTP-Posting-Host: 194.109.248.204 X-Trace: 1037913254 news.xs4all.nl 46603 194.109.248.204:1413