Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Wie kann man hier die Laufzeit mit einem Blick erkennen?
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Wie kann man hier die Laufzeit mit einem Blick erkennen?
ProfSnape
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 12.10.2019
Mitteilungen: 59
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-11-22


Hi!
Es geht um den countSort:



Ich frage mich, wie man in dieser Implementierung direkt sieht,
dass die laufzeit Theta(2k + 4n) ist?

Ich sehe dort z.B. folgendes:
1.) bei der Initilaisierung mit Nullen -> = 1k
2.) Innerhalb der 2ten for-Schleife wird das array n-mal durchlaufen.
       -> = 1n  
3.) in der while-Schleife innerhalb der letzten for-Schleife,
   die wiederum das Array n-mal durchläuft -> = n + k
   Trotz innerer while-loop wohl nicht n*k, da ja das j bzgl.
   dem bin-Behälter nicht jedes mal bei jedem weiterem äußerem
   Schleifendurchgang bei 0 startet, sondern sich die Position,
   an der man war, gemerkt wird - richtig?

Macht für mich gesamt: Theta(2n + 2k)
Wieso ist es aber 4n?

Möchte einfach mal meine Intuition für solche Laufzeit-Geschichten verbessern  - evtl. kann ja Jemand helfen:)

Lg
ProfSnape




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ProfSnape
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 12.10.2019
Mitteilungen: 59
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, vom Themenstarter, eingetragen 2020-11-26


Keiner eine Idee?:(

Anscheinend soll die letzte for-Schleife (incl. der while-Schleife)
bzgl. der Laufzeit direkt mal 3n darstellen - stimmt das?
Falls ja, wieso? ich sehe das dort nicht.

Höchstens 2n sähe ich noch:
1n für die n-mal häufige Zuweisung 'a[i] = j' und
noch 1 n für den Umstand, dass bin[j] insgesamt wohl n-mal dekrementiert wird.

Wo kommt das 3te n her?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 1887
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-11-26


Für die Bestimmung der Vorfaktoren vor $n$ und $k$ in $\Theta(\nu\cdot n+\kappa\cdot k)$ gibt es keinen eindeutig richtigen Weg, denn diese Vorfaktoren messen ja den Aufwand, den ein Schleifendurchlauf erfordert. Und während man die Zahl der Durchläufe einfach zählen kann, müsste man hier das Programm mit einer Stoppuhr in der Hand beobachten.

In der Musterlösung wurde als Maß für den Aufwand einfach die Zahl der Statements im Inneren der Schleife gewählt. Für $k$ sind das 2 (nämlich "bin[i]=0" und "j++") und für $n$ sind das 4 (nämlich "bin[a[i]]++", "bin[j]==0", "a[i]=j", "bin[j]--").

Das ist aber nur eine von vielen Möglichkeiten, den Aufwand zu quantifizieren.

Und für das Endergebnis spielen diese Vorfaktoren auch keine Rolle mehr. Wichtig ist nur, dass es sich um irgendwelche Konstanten handelt (die also nicht mehr von $n$ und $k$ abhängen), und dass diese Konstanten nicht verschwinden.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2694
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-11-26


Die Zählweise wirkt auf mich sehr ungewöhnlich, weshalb ich mir schwertue, hier zu antworten.

Ich vermute auch, dass die zweite Schleife n-mal gezählt werden soll, wobei man dann hinterfragen muss, warum die innere while-Schleife als eine Anweisung zählen sollte.

Daneben müsste man hinterfragen, warum Anweisungen in den Schleifenblöcken, nicht jedoch Anweisungen und Vergleiche in den Schleifenköpfen zählen sollen.




[Die Antwort wurde nach Beitrag No.1 begonnen.]


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ProfSnape
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 12.10.2019
Mitteilungen: 59
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-11-26


2020-11-26 13:31 - zippy in Beitrag No. 2 schreibt:

Und für das Endergebnis spielen diese Vorfaktoren auch keine Rolle mehr. Wichtig ist nur, dass es sich um irgendwelche Konstanten handelt (die also nicht mehr von $n$ und $k$ abhängen), und dass diese Konstanten nicht verschwinden.

Das stimmt, aber evtl. spielt es für die Klausur eine Rolle xD

Dank trotzdem, und auch an derEinfaeltige.^^




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6699
Herkunft: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-11-26


2020-11-26 13:39 - DerEinfaeltige in Beitrag No. 3 schreibt:
Daneben müsste man hinterfragen, warum Anweisungen in den Schleifenblöcken, nicht jedoch Anweisungen und Vergleiche in den Schleifenköpfen zählen sollen.
Weil konstante Summanden erst recht unter dem $\Theta$ verschwinden.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 1887
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-11-27


2020-11-26 23:51 - Kitaktus in Beitrag No. 5 schreibt:
2020-11-26 13:39 - DerEinfaeltige in Beitrag No. 3 schreibt:
Daneben müsste man hinterfragen, warum Anweisungen in den Schleifenblöcken, nicht jedoch Anweisungen und Vergleiche in den Schleifenköpfen zählen sollen.
Weil konstante Summanden erst recht unter dem $\Theta$ verschwinden.

Es handelt sich nicht um konstante Summanden. Die Anweisungen "i<n" und "i++" in dem Kopf der for-Schleife for(i=0;i<n;i++) skalieren genauso mit $n$ wie die Anweisung "bin[a[i]]++" im Schleifenblock. Trotzdem wird nur letztere gezählt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6699
Herkunft: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-11-27


Wenn Du die Operationen meinst, dann hast Du nicht unrecht (*). Deswegen sollte ja immer genau angegeben sein, was man eigentlich zählt (Vergleiche, Gleitkommaoperationen, Speicherzugriffe, ...) und deswegen benutzt man häufig die Landauschen O-Symbole.

(*) Da ich häufig in Interpreter-Sprachen programmiere, macht es für mich schon einen gehörigen Unterschied, ob der Befehl im Schleifenkopf steht (wird nur einmal in Maschinen-Code übersetzt), oder ob er im Schleifenrumpf steht (wird bei jedem Durchlauf übersetzt).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ProfSnape hat die Antworten auf ihre/seine Frage gesehen.
ProfSnape hatte hier bereits selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]