| |
| Autor |
 Wie kann man hier die Laufzeit mit einem Blick erkennen? |
|
ProfSnape
Aktiv 
Dabei seit: 12.10.2019
Mitteilungen: 54
 |
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
|
 Notiz  Profil
 Quote
 Link |
ProfSnape
Aktiv 
Dabei seit: 12.10.2019
Mitteilungen: 54
|      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?
|
Notiz Profil
Quote
Link |
zippy
Senior 
Dabei seit: 24.10.2018
Mitteilungen: 1780
 | 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.
|
Notiz Profil
Quote
Link |
DerEinfaeltige
Senior 
Dabei seit: 11.02.2015
Mitteilungen: 2623
 | 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 -
|
Notiz Profil
Quote
Link |
ProfSnape
Aktiv
Dabei seit: 12.10.2019
Mitteilungen: 54
| 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.^^
|
Notiz Profil
Quote
Link |
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6653
Herkunft: Niedersachsen
 | 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.
|
Notiz Profil
Quote
Link |
zippy
Senior
Dabei seit: 24.10.2018
Mitteilungen: 1780
| 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.
|
Notiz Profil
Quote
Link |
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6653
Herkunft: Niedersachsen
| 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).
|
Notiz Profil
Quote
Link |
|
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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
