Springen naar inhoud

Bubble Sort Complexiteit


  • Log in om te kunnen reageren

#1

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 05 april 2013 - 00:05

Hey,

Bubble sort, het alom bekende algortime, daarvan zou ik graag eens berekenen willen hoeveel keer de als lus wordt aangeroepen (regel 4).
Ik heb getracht dit een som te plaatsen en dit is mijn resultaat: LaTeX .

Ik vermoed dat ik hier ergens te kort door de bocht ga maar ik weet niet precies waar.
Volgens Wolfram Alpha zou het dit moeten zijn: http://tinyurl.com/w...amalphauitkomst

Bubble sort.png

Iemand die me kan helpen?

Dank bij voorbaat,
Roger

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 05 april 2013 - 11:29

Waarom zijn de grenzen bij het tweede somteken niet afhankelijk van i? (dat zijn ze in de pseudocode immers wel.)

#3

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 05 april 2013 - 11:32

Maakt dat iets uit of ik nu de lus uitvoer door iedere keer mijn j min 1 te doen of gewoon van i + 1 naar j gaan? Komt dat niet op hetzelfde neer?

#4

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2382 berichten
  • Ervaren gebruiker

Geplaatst op 05 april 2013 - 11:36

Je pseudocode is niet duidelijk omdat je nergens aangeeft hoe i en j veranderen. Ik neem aan dat je in de buitenste lus telkens i met 1 verhoogt, terwijl je in de binnenste lus telkens j met 1 verlaagt?
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#5

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 05 april 2013 - 11:40

Je pseudocode is niet duidelijk omdat je nergens aangeeft hoe i en j veranderen. Ik neem aan dat je in de buitenste lus telkens i met 1 verhoogt, terwijl je in de binnenste lus telkens j met 1 verlaagt?

Dat is toch duidelijk?

Opmerking moderator :

Verplaatst naar programmeren.

#6

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 05 april 2013 - 11:40

Inderdaad, maar om op EvilBro zijn vraag verder te gaan, ik weet niet of het mogelijk is om bij een sommatie j--; te doen, vandaar dat ik ze heb omgewisseld, naar mijn mening zal dit geen verschil uitmaken, of sla ik hier de bal mis?

#7

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 05 april 2013 - 11:52

Die LaTeX klopt niet, maar je kan het veel intuïtiever afleiden.

Algemeen loopt de binnenste loop van i+1 tot n, dus n-i herhalingen zoals je zelf al doorhad. Die doe je voor i = 1 tot n.

Zet dat in een som en reken uit: LaTeX

#8

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 05 april 2013 - 12:09

Ik heb het eventjes volledig uitgewerkt: LaTeX .
Ik snap niet goed waarom je gaat tot n en niet (n - 1). In de pseudo-code staat toch beschreven dat je moet gaan tot (n-1)?

#9

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 05 april 2013 - 12:36

Pseudocode naar som (volgens mij gewoon een kwestie van de grenzen lezen in de code):
LaTeX
Zoals je ziet is hier de tweede som afhankelijk van i. Dit was bij jou niet het geval (en dat is hetgeen ik aanstipte, maar jij had dat kennelijk niet helemaal goed begrepen).

Een andere manier om het te benaderen: Stel dat je een rij gaat sorteren die precies verkeerd om begint. Je begint dan bij het achterste element (= het kleinste element). Dit element wordt dan dus met alle andere elementen vergeleken om zo uiteindelijk op de eerste plek uit te komen. Dit zijn (n-1) vergelijkingen. Vervolgens wordt het nieuwe achterste element (het op een na kleinste element) met alle andere elementen vergeleken (behalve de eerste) om uiteindelijk op de tweede positie te komen. Ga zo door met alle andere elementen. Hopelijk is het niet lastig om in te zien dat zo alle elementen precies 1x met elkaar vergeleken worden.
Hoeveel vergelijkingen zijn er met n elementen? Elk element wordt met (n-1) andere elementen vergeleken, dus:
LaTeX
Maar nu maak je geen onderscheid tussen de vergelijking (1 met 2) en (2 met 1). Je telt alle paren dus dubbel. Dit leidt tot:
LaTeX

Veranderd door EvilBro, 05 april 2013 - 12:43


#10

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 05 april 2013 - 13:00

Ik verstond zoals je zegt niet goed hoe je die afhankelijkheid in een som moest zetten.

Ter volledigheid:
LaTeX

LaTeX waarbij LaTeX , dat zal ons opleveren:
LaTeX
LaTeX
LaTeX

Dan krijgen we: LaTeX


LaTeX
LaTeX
LaTeX
LaTeX

LaTeX
Dit is echter heel iets anders als ik n neem in plaats van (n-1).

Veranderd door Energyfellow, 05 april 2013 - 13:08


#11

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 05 april 2013 - 13:55

Ik snap niet goed waarom je gaat tot n en niet (n - 1). In de pseudo-code staat toch beschreven dat je moet gaan tot (n-1)?

Dat heb ik dan even fout gelezen ;)

#12

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 05 april 2013 - 14:04

Maar het rare is dat jouw antwoord het correcte is ... namelijk: LaTeX .

Geplaatste afbeelding

Veranderd door Energyfellow, 05 april 2013 - 14:05


#13

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 05 april 2013 - 14:19

Dan zullen we eens naar de berekening kijken he. Met de juiste grenzen wordt het:

LaTeX
De eerste som valt weer makkelijk uit te rekenen, voor de volgende pas ik een trucje toe. Ik laat de som gaan tot n en trek compenseer dan buiten de som die extra term:
LaTeX
LaTeX
LaTeX
LaTeX
LaTeX

Merk op dat dit ook gewoon logisch is, waaraan is de term voor i=n gelijk? ;)

#14

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 05 april 2013 - 14:20

Nog een keertje proberen:
LaTeX

Edit: ah, ik zie dat die suggestie al gedaan is...

Veranderd door EvilBro, 05 april 2013 - 14:21


#15

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 05 april 2013 - 14:52

@Xenion, ik snap je manier van redeneren en is uiteindelijk ook logisch (een trucje om zeker te onthouden :)).

@EvilBro:
LaTeX
LaTeX
LaTeX
LaTeX
LaTeX
LaTeX

Bedankt voor alles EvilBro en Xenion :D.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures