Antworte auf:  Wie kann man hier die Laufzeit mit einem Blick erkennen? von ProfSnape
Forum:  Algorithmen / Datenstrukturen, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6708
Herkunft: Niedersachsen

 Beitrag No.7, eingetragen 2020-11-27 16:43    [Diesen Beitrag zitieren]

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).


zippy
Senior
Dabei seit: 24.10.2018
Mitteilungen: 1925
 Beitrag No.6, eingetragen 2020-11-27 00:15    [Diesen Beitrag zitieren]

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.


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6708
Herkunft: Niedersachsen

 Beitrag No.5, eingetragen 2020-11-26 23:51    [Diesen Beitrag zitieren]

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.


ProfSnape
Aktiv
Dabei seit: 12.10.2019
Mitteilungen: 83
 Beitrag No.4, eingetragen 2020-11-26 15:42    [Diesen Beitrag zitieren]

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.^^



DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2715
 Beitrag No.3, eingetragen 2020-11-26 13:39    [Diesen Beitrag zitieren]

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.]


zippy
Senior
Dabei seit: 24.10.2018
Mitteilungen: 1925
 Beitrag No.2, eingetragen 2020-11-26 13:31    [Diesen Beitrag zitieren]

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.


ProfSnape
Aktiv
Dabei seit: 12.10.2019
Mitteilungen: 83
 Beitrag No.1, eingetragen 2020-11-26 13:18    [Diesen Beitrag zitieren]

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?


ProfSnape
Aktiv
Dabei seit: 12.10.2019
Mitteilungen: 83
 Themenstart: 2020-11-22 13:12    [Diesen Beitrag zitieren]

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



 
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]