Article View: be.comp.programming
Article #6439Re: tijdscomplexiteit : sorteren in een cirkel
From: Nicolas Barbier
Date: Mon, 02 Dec 2002 15:28
Date: Mon, 02 Dec 2002 15:28
26 lines
2316 bytes
2316 bytes
Dieter D'Hoker wrote: > 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 ... Niet echt een goed beschreven probleem, maarja :-) - Verschuivingen kunnen enkel 1 voor 1: als het een rij zou zijn zou het hierdoor minstens (in het slechtste geval) orde n^2 zijn. - Het feit dat het een cirkel is betekent 3 dingen: Je mag "door de bovenkant schuiven" zodat je terug onderaan aankomt (en andersom), je mag (veronderstel ik) de orientatie van de gesorteerde cirkel kiezen (gesorteerd met of tegen de klok), en je mag het "beginpunt" kiezen (waar na het grootste terug het laagste komt). Geen enkele van deze 3 eigenschappen veranderen de orde volgens mij, dus nog altijd (in het slechtste geval) orde n^2. (Hmm bij nader inzien lijkt dit niet echt een antwoord op je vraag. Mja anyway.. :-) -- Nicolas Barbier
Technical Details
Message-ID:
<3deb7c27$0$30451$afc38c87@sisyphus.news.be.easynet.net>Path:
arc1-ca.pugleaf.net!archiver1.google.com!news1.google.com!sn-xit-02!sn-xit-06!sn-xit-04!supernews.com!news.maxwell.syr.edu!newsfeed.online.be!feed1.news.be.easynet.net!sisyphus.news.be.easynet.net!not-for-mailReferences:
<3ddd4ca5$0$46603$e4fe514c@news.xs4all.nl>Show Full Headers
Complete Article Headers
X-Google-Language: DUTCH,ASCII-7-bit X-Google-Thread: 107324,46214dff648db5b1 X-Google-Attributes: gid107324,public X-Google-Thread: fcea4,46214dff648db5b1 X-Google-Attributes: gidfcea4,public X-Google-Thread: f7e01,46214dff648db5b1 X-Google-Attributes: gidf7e01,public X-Google-Thread: f5500,46214dff648db5b1 X-Google-Attributes: gidf5500,public X-Google-ArrivalTime: 2002-12-02 07:28:40 PST Path: arc1-ca.pugleaf.net!archiver1.google.com!news1.google.com!sn-xit-02!sn-xit-06!sn-xit-04!supernews.com!news.maxwell.syr.edu!newsfeed.online.be!feed1.news.be.easynet.net!sisyphus.news.be.easynet.net!not-for-mail Message-ID: <3deb7c27$0$30451$afc38c87@sisyphus.news.be.easynet.net> From: Nicolas Barbier <anti@spam.invalid> Subject: Re: tijdscomplexiteit : sorteren in een cirkel Newsgroups: be.comp.programming,be.science,nl.comp.programmeren,nl.wetenschap Followup-To: be.comp.programming Date: Mon, 02 Dec 2002 16:28:29 +0100 References: <3ddd4ca5$0$46603$e4fe514c@news.xs4all.nl> User-Agent: KNode/0.6.1 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7Bit Lines: 27 Organization: [ posted via Easynet Belgium ] NNTP-Posting-Host: 213.193.183.45 X-Trace: 1038842919 30451 213.193.183.45 X-Complaints-To: abuse@be.easynet.net