Thread View: be.comp.programming
21 messages
21 total messages
Started by Dieter D'Hoker
Thu, 21 Nov 2002 21:14
tijdscomplexiteit : sorteren in een cirkel
Author: 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
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Atrius
Date: Thu, 21 Nov 2002 21:19
Date: Thu, 21 Nov 2002 21:19
5 lines
1555 bytes
1555 bytes
<serieuze knip> lol, weer ene die z'n huiswerk niet zelf kan maken ;-)
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Dieter D'Hoker
Date: Thu, 21 Nov 2002 21:42
Date: Thu, 21 Nov 2002 21:42
21 lines
2013 bytes
2013 bytes
"Atrius" <atrius.InvalidPart@pandora.be> wrote in message news:X5cD9.12192$Ti2.2472@afrodite.telenet-ops.be... > > <serieuze knip> > > > lol, weer ene die z'n huiswerk niet zelf kan maken ;-) > > Is helemaal geen huiswerk hoor :) Probleem komt uit een "bezinnings-dag" van het middelbaar , praktisch gezien blijkt daar methode b het beste te lukken , nu vraag ik mij af hoe het zit als je dit algoritmisch bekijkt ... -- Dieter D'Hoker http://dieter.dhoker.com/ news:free.nl.dieter.dhoker & news:alt.nl.fan.dieter.dhoker
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Sander Nijdam
Date: Thu, 21 Nov 2002 22:07
Date: Thu, 21 Nov 2002 22:07
23 lines
2061 bytes
2061 bytes
Laatst tikte "Dieter D'Hoker" <webmaster@neverseenbefore.com>: > "Atrius" <atrius.InvalidPart@pandora.be> wrote in message > news:X5cD9.12192$Ti2.2472@afrodite.telenet-ops.be... > > > > <serieuze knip> > > > > > > lol, weer ene die z'n huiswerk niet zelf kan maken ;-) > > > > > > Is helemaal geen huiswerk hoor :) > > Probleem komt uit een "bezinnings-dag" van het middelbaar , > praktisch gezien blijkt daar methode b het beste te lukken , > nu vraag ik mij af hoe het zit als je dit algoritmisch bekijkt ... Bekijk hier eens een grote groep sorteermethoden: http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html Inclusief programmeervoorbeelden. Sander...
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Pieter Philippaerts
Date: Thu, 21 Nov 2002 22:21
Date: Thu, 21 Nov 2002 22:21
38 lines
3112 bytes
3112 bytes
"Dieter D'Hoker" <webmaster@neverseenbefore.com> wrote in message news:3ddd4ca5$0$46603$e4fe514c@news.xs4all.nl... > 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 ... Als je deze lus blijft uitvoeren totdat er niemand meer veplaatst wordt, dan gaat ze in een oneindige lus [aangezien de mensen in een cirkel staan; als ze in een rij zouden staan had dit wel gewerkt]. > 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 ... Deze methode [selection sort] heeft een gemiddelde complexiteit van O((n-1)(n-2)...(1)) = O(n(n+1)/2) = O(n^2). > Iemand een idee ? En een formule in functie van n (n = aantal personen = > aantal plaatsen in de cirkel) om dit te onderbouwen ? Persoonlijk zou ik eerst het hoogste [of het laagste] element zoeken in je rij [O(n)] en dan een aangepaste bubble sort doen [methode a]. De complexiteit van het slechtste geval is nog steeds O(n^2), maar in het gemiddelde geval gaat die veel beter uitkomen dan een selection sort. Aangezien de complexiteit van je sorteer algoritme hoger is dan O(n) maakt die eerste zoek operatie van het hoogste/laagste element niets uit. Trouwens, als je eens wil _zien_ hoe snel de verschillende sorteer methodes zijn, raad ik je aan de volgende pagina eens te bezoeken: http://www.cs.kuleuven.ac.be/~kdv/mi0001/hoorcolleges/SORTING/AllFlat/sortin g-demo.html Mvg, Pieter Philippaerts
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Suzan Foster
Date: Thu, 21 Nov 2002 22:24
Date: Thu, 21 Nov 2002 22:24
22 lines
1877 bytes
1877 bytes
In nl.comp.programmeren Dieter D'Hoker <webmaster@neverseenbefore.com> 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 ... : 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 ... deze conditie komt toch altijd voor in een aaneengesloten cirkel lijkt mij. blijft er dus altijd iemand schuifelen. groetjes, su.
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Dieter D'Hoker
Date: Thu, 21 Nov 2002 22:50
Date: Thu, 21 Nov 2002 22:50
38 lines
2654 bytes
2654 bytes
"Suzan Foster" <foz@xs1.xs4all.nl> wrote in message news:3ddd5d2c$0$46609$e4fe514c@news.xs4all.nl... > In nl.comp.programmeren Dieter D'Hoker <webmaster@neverseenbefore.com> 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 ... > > : 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 ... > > deze conditie komt toch altijd voor in een aaneengesloten cirkel > lijkt mij. blijft er dus altijd iemand schuifelen. > je bepaald op voorand ook de laagste persoon , en die zet je net zoals in b als beginpunt , was ik er vergeten bij te zeggen ... Je maakt er dus eignelijk een rij van ipv. een cirkel ... -- Dieter D'Hoker http://dieter.dhoker.com/ news:free.nl.dieter.dhoker & news:alt.nl.fan.dieter.dhoker
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Dieter D'Hoker
Date: Thu, 21 Nov 2002 22:50
Date: Thu, 21 Nov 2002 22:50
27 lines
2305 bytes
2305 bytes
"Pieter Philippaerts" <Pieter@removethis.mentalis.org> wrote in message news:1037917053.179003@seven.kulnet.kuleuven.ac.be... > "Dieter D'Hoker" <webmaster@neverseenbefore.com> wrote in message > news:3ddd4ca5$0$46603$e4fe514c@news.xs4all.nl... > > 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 ... > > Als je deze lus blijft uitvoeren totdat er niemand meer veplaatst wordt, dan > gaat ze in een oneindige lus [aangezien de mensen in een cirkel staan; als > ze in een rij zouden staan had dit wel gewerkt]. je bepaald op voorand ook de laagste persoon , en die zet je net zoals in b als beginpunt , was ik er vergeten bij te zeggen ... Je maakt er dus eignelijk een rij van ipv. een cirkel ... -- Dieter D'Hoker http://dieter.dhoker.com/ news:free.nl.dieter.dhoker & news:alt.nl.fan.dieter.dhoker
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Dieter D'Hoker
Date: Thu, 21 Nov 2002 22:53
Date: Thu, 21 Nov 2002 22:53
41 lines
2773 bytes
2773 bytes
"Sander Nijdam" <sandernWilGeenSpam@dds.nl> wrote in message news:p4mqtuc26g29fjr49mj69qn05kft9neil4@4ax.com... > Laatst tikte "Dieter D'Hoker" <webmaster@neverseenbefore.com>: > > > "Atrius" <atrius.InvalidPart@pandora.be> wrote in message > > news:X5cD9.12192$Ti2.2472@afrodite.telenet-ops.be... > > > > > > <serieuze knip> > > > > > > > > > lol, weer ene die z'n huiswerk niet zelf kan maken ;-) > > > > > > > > > > Is helemaal geen huiswerk hoor :) > > > > Probleem komt uit een "bezinnings-dag" van het middelbaar , > > praktisch gezien blijkt daar methode b het beste te lukken , > > nu vraag ik mij af hoe het zit als je dit algoritmisch bekijkt ... > > Bekijk hier eens een grote groep sorteermethoden: > http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html > Inclusief programmeervoorbeelden. > ja die ken ik , maar die kun je neit klakkeloos toepassen op het voorbeeld dacht ik , want hier wordt geeen rekning mee gehouden dat het aantal plaatsen dat je een element verschuift , meetelt in de tijdscomplexiteit ? In een computerprogramma zal het neit veel uitmaken als je bv. rij[1] verwisselt met rij[10000] , maar hier wel , want je moet hiervoor 10000 verplaatsingen doorlopen ? -- Dieter D'Hoker http://dieter.dhoker.com/ news:free.nl.dieter.dhoker & news:alt.nl.fan.dieter.dhoker
Re: tijdscomplexiteit : sorteren in een cirkel
Author: J. J. Lodder
Date: Thu, 21 Nov 2002 23:23
Date: Thu, 21 Nov 2002 23:23
9 lines
1385 bytes
1385 bytes
Dieter D'Hoker <webmaster@neverseenbefore.com> wrote: > stel je hebt een cirkel van n - personen , > en je wilt die rangschikken volgen geboortedatum , gewicht , lengte , je > kiest maar ... Waarom kijk je zelf niet even bij Knuth? Jan
Re: tijdscomplexiteit : sorteren in een cirkel
Author: dirk selis
Date: Fri, 22 Nov 2002 05:39
Date: Fri, 22 Nov 2002 05:39
56 lines
2931 bytes
2931 bytes
Simpel , bekijk een cirkel in drie dimensies als ge sorteert op drie parameters . De x as is de sortering volgens lengte , de y as de sortering volgens gewicht en de z as de sortering volgens geboortedatum . dirk "Dieter D'Hoker" <webmaster@neverseenbefore.com> wrote in message news:3ddd4ca5$0$46603$e4fe514c@news.xs4all.nl... > 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 > > >
OT: follow-ups (was Re: tijdscomplexiteit : sorteren in een cirkel)
Author: Christopher Ranschaert
Date: Fri, 22 Nov 2002 08:02
Date: Fri, 22 Nov 2002 08:02
10 lines
1843 bytes
1843 bytes
On Thu, 21 Nov 2002 22:14:02 +0100, Dieter D'Hoker wrote: Dieter, wanneer ga je eens beginnen met Follow-ups te zetten. Multiposten is certainly not done, cross-posten is al wat beter, maar zet er dan toch tenminste een follow-up bij, zodat alle antwoorden in dezelfde newsgroup terechtkomen. Merci in advance Chris
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Pros Robaer
Date: Fri, 22 Nov 2002 19:14
Date: Fri, 22 Nov 2002 19:14
10 lines
1584 bytes
1584 bytes
Dieter D'Hoker schreef: > Je maakt er dus eignelijk een rij van ipv. een cirkel ... Waarom dan die rare cirkel? --- Vriendelijke GNUtjes, Pros
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Cor Gest
Date: Fri, 22 Nov 2002 20:21
Date: Fri, 22 Nov 2002 20:21
21 lines
2051 bytes
2051 bytes
Pros Robaer <pros@village.uunet.be> writes: > Dieter D'Hoker schreef: > > > Je maakt er dus eignelijk een rij van ipv. een cirkel ... > > Waarom dan die rare cirkel? Ach een kromme rij om een gezamelijk middelpunt met gelijkblijvende afstand bedoelt ie dus.... een ietwat kromme uitleg dus. cor -- Sed quis custodiet ipsos custodes Are You Sure ? ||YES||DO-IT||CHECK-IT|| Operatingsystem is just a name thou giveth to the rest of thy idiosyncratic machine-based features left out of thoueth editor. Knowlegde should have free access to people http://thefreeworld.net
Re: follow-ups (was Re: tijdscomplexiteit : sorteren in een cirkel)
Author: Dieter D'Hoker
Date: Fri, 22 Nov 2002 21:31
Date: Fri, 22 Nov 2002 21:31
38 lines
2930 bytes
2930 bytes
"Christopher Ranschaert" <remove-X@email.ad> wrote in message news:pan.2002.11.22.08.02.29.384726@email.ad... > On Thu, 21 Nov 2002 22:14:02 +0100, Dieter D'Hoker wrote: > > Dieter, wanneer ga je eens beginnen met Follow-ups te zetten. Multiposten > is certainly not done, cross-posten is al wat beter, maar zet er dan toch > tenminste een follow-up bij, zodat alle antwoorden in dezelfde newsgroup > terechtkomen. Daar ben ik het helemaal neit mee eens , multiposten is inderdaad niet goed , maar crossposten daar zie ik geen enkel probleem in , als het in alle groepen on-topic is ... Er wordt bv. geen extra serverruimte verspilt ... FO is alleen nuttig als de discussie in een bepaalde groep off-topic zou worden ... Verder is FO ook gewoonweg irritant , immers als iemand de discussie verder zou willen volgen zou hij op een andere groep moeten subscriben , verder vind ik FO verwarrend voor de gerbuiekr , zeker en vast als je in de biody van het bericht niet aangeeft dat er een FO is naar die bepaalde groep , zoals jij bv. deed . (daaromd at ik je FO niet respecteer bij deze , ze is trouwens niet naar de jusite groep gezet , be.comp.programmign heef tniets met deze discussie te maken ) FO set naar nl.newsgroups & nl.internet.misbruik (gelieve dus integraal te quoten zodat ze daar weten waarover het gaat als je reageerd) -- Dieter D'Hoker http://dieter.dhoker.com/ news:free.nl.dieter.dhoker & news:alt.nl.fan.dieter.dhoker
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Dieter D'Hoker
Date: Fri, 29 Nov 2002 05:03
Date: Fri, 29 Nov 2002 05:03
24 lines
2123 bytes
2123 bytes
"Pros Robaer" <pros@village.uunet.be> wrote in message news:4997366.EoZ9vM6j8K@eljudnir... > Dieter D'Hoker schreef: > > > Je maakt er dus eignelijk een rij van ipv. een cirkel ... > > Waarom dan die rare cirkel? > > Omdat die bij mogelijkheid B wel voordelig uitkomt aangezien , het aantal verplaatsingen ook telt (wat bijd e classieke sorteeralgoritmes niet het geval is ) ... moet iemand zich in een cirkel verplaatsen naar 1 punt dat willekeurig gekozen is , dan hoeft hij maximaal n / 2 verplaatsingen te ondergaan , wil hij zich in een evengrote rij verplaatsne moet hij maximaal n verplaatsingen ondergaan ... -- Dieter D'Hoker http://dieter.dhoker.com/ news:free.nl.dieter.dhoker & news:alt.nl.fan.dieter.dhoker
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Michel
Date: Fri, 29 Nov 2002 05:08
Date: Fri, 29 Nov 2002 05:08
29 lines
2307 bytes
2307 bytes
Als ie dat had gezegd dan hadden jullie met z'n allen geroepen dat het om een cirkel ging, nietwaar? "Cor Gest" <cor@clsnet.nl> wrote in message news:87smxt8if6.fsf@cleopatra.clsnet.nl... > Pros Robaer <pros@village.uunet.be> writes: > > > Dieter D'Hoker schreef: > > > > > Je maakt er dus eignelijk een rij van ipv. een cirkel ... > > > > Waarom dan die rare cirkel? > > Ach een kromme rij om een gezamelijk middelpunt met gelijkblijvende > afstand bedoelt ie dus.... > > een ietwat kromme uitleg dus. > > cor > > > -- > Sed quis custodiet ipsos custodes Are You Sure ? ||YES||DO-IT||CHECK-IT|| > Operatingsystem is just a name thou giveth to the rest of thy idiosyncratic > machine-based features left out of thoueth editor. > Knowlegde should have free access to people http://thefreeworld.net
Re: tijdscomplexiteit : sorteren in een cirkel
Author: sumteufel
Date: Fri, 29 Nov 2002 06:23
Date: Fri, 29 Nov 2002 06:23
35 lines
2541 bytes
2541 bytes
Is dit geen puzzel? "Michel" <je@weetwel.ofniet> schreef in bericht news:as6se0$230$1@ncc1701.cistron.net... > Als ie dat had gezegd dan hadden jullie met z'n allen geroepen dat het om > een cirkel ging, nietwaar? > > "Cor Gest" <cor@clsnet.nl> wrote in message > news:87smxt8if6.fsf@cleopatra.clsnet.nl... > > Pros Robaer <pros@village.uunet.be> writes: > > > > > Dieter D'Hoker schreef: > > > > > > > Je maakt er dus eignelijk een rij van ipv. een cirkel ... > > > > > > Waarom dan die rare cirkel? > > > > Ach een kromme rij om een gezamelijk middelpunt met gelijkblijvende > > afstand bedoelt ie dus.... > > > > een ietwat kromme uitleg dus. > > > > cor > > > > > > -- > > Sed quis custodiet ipsos custodes Are You Sure ? > ||YES||DO-IT||CHECK-IT|| > > Operatingsystem is just a name thou giveth to the rest of thy > idiosyncratic > > machine-based features left out of thoueth editor. > > Knowlegde should have free access to people > http://thefreeworld.net > >
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Pros Robaer
Date: Fri, 29 Nov 2002 18:22
Date: Fri, 29 Nov 2002 18:22
14 lines
1940 bytes
1940 bytes
Dieter D'Hoker schreef: > moet iemand zich in een cirkel verplaatsen naar 1 punt dat willekeurig > gekozen is , dan hoeft hij maximaal n / 2 verplaatsingen te ondergaan , > wil hij zich in een evengrote rij verplaatsne moet hij maximaal n > verplaatsingen ondergaan ... Nou heb ik 'm! --- Vriendelijke GNUtjes, Pros (beter laat dan nooit)
Re: tijdscomplexiteit : sorteren in een cirkel
Author: Dieter D'Hoker
Date: Sun, 01 Dec 2002 02:40
Date: Sun, 01 Dec 2002 02:40
13 lines
1854 bytes
1854 bytes
"sumteufel" <sumteufel@hotmail.com> wrote in message news:as714a$ocn$2@nl-news.euro.net... > Is dit geen puzzel? > zal ik hem eens op alt.nl.raadsels postten ? :) -- Dieter D'Hoker http://dieter.dhoker.com/ news:free.nl.dieter.dhoker & news:alt.nl.fan.dieter.dhoker
Re: tijdscomplexiteit : sorteren in een cirkel
Author: 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
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads