Laufzeit bestimmen



  • Hallo,

    ich habe eine Frage zur Laufzeitbestimmung von Algorithmen.
    Generell gilt, so wie ich das gelernt habe folgendes:
    (falls ich das richtig verstanden habe)

    -eine for-Schleife hat eine Laufzeit von n, also O(n)
    -zwei for-Schleifen ineinander haben eine Laufzeit von n2, also O(n2)
    -rekursiver Aufruf, in dem die Hälfte der Liste übergeben wird ist logarithmisch, O(log(n)),
    -eine rekursiver logaritihmischer Aufruf innerhalb einer for-Schleife hat O(n*log(n)),

    -ein rekursiver logarithmischer Aufruf und danach eine for-Schleife hat, würde ich sagen n+log(n), also O(n+log(n)). "n Plus log(n)" deshalb, da es ja nach dem rekursiven Aufruf ist.

    Nun mein Verständnisproblem:
    Allerdings hat zB Mergesort O(n*log(n)). Das wird umgeformt aus T(n)= T(n/2)+ T(n/2) + n.

    Aber jetzt weiß ich nicht,ob meine obigen Annahmen richtig sind. Da ja nach MergeSort der rekursive Aufruf und danach eine Schleife die Laufzeit O(nlog(n)) und nicht O(n+log(n) ergibt.
    Bin verwirrt.
    Kann man denn die Laufzeit nicht so wie oben genannt ablesen? Also kann man auch ablesen, dass MergeSort O(n
    log(n)) ist.
    Und was für eine Laufzeit hat denn dann ein rekursiver Aufruf (mit n/2 als Parameter) innerhalb einer for-Schleife, O(n*(log(n))??

    Wäre toll, wenn mir jmd helfen könnte.



  • Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (alle ISO-Standards) in das Forum Rund um die Programmierung verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.



  • Deine Analyse vergisst, dass in dem rekursiven Aufruf ja auch wieder eine Schleife drin ist, die Laufzeit dort also nicht logarithmisch sondern linear ist. Allerdings wird dann nur noch die Hälfte der Elemente bearbeitet. Genau das besagt ja die Rekurrenz. Die kann man nun lösen. Dazu gibt es eine ganze Reihe von Verfahren. Letztlich wurden die Rekurrenzen genau deswegen eingeführt, weil man damit solche Analysen gut machen kann. Dass so ein oberflächliches Regelwerk schnell zu falschen Abschätzungen führt hast Du ja selbst gemerkt.



  • -eine for-Schleife hat eine Laufzeit von n, also O(n)
    -zwei for-Schleifen ineinander haben eine Laufzeit von n2, also O(n2)

    Richtig, wenn die Operationen die in der Schleife ausgeführt werden, in O(1)\mathcal{O}(1) berechenbar sind.

    n+log(n), also O(n+log(n))

    … also O(n)\mathcal{O}(n). Nicht vergessen: b,cR+  logbn=o(nc)\forall b,c \in \mathbb{R}^+~~ \log_b n = o(n^c). I.e. Logarithmen in einer Summe mit irgendeinem letztlich steigenden Polynom kannste vernachlässigen.

    Da ja nach MergeSort der rekursive Aufruf und danach eine Schleife die Laufzeit O(n*log(n)) und nicht O(n+log(n) ergibt.
    Bin verwirrt.

    Schuss ins Blaue: Dass weitere Schleifen in jedem rekursiven Durchlauf ebenfalls durchlaufen werden, hast du verinnerlicht? I.e. es werden O(logn)\mathcal{O}(\log n) Schleifen durchlaufen, nicht nur eine.



  • @Arcoth: das wäre immer noch linear...

    Wie ich schon sagte: mit rekurrenzen vermeidet man solche adhoc-Fehleinschätzungen. 😉



  • Jester schrieb:

    @Arcoth: das wäre immer noch linear...

    Wovon redest du?



  • Wenn nur log(N) Schleifen laufen würde, und jede Schleife nur 50% der Schleifendurchläufe der "darüberliegenden" Schleife (Ebene) machen würde, dann wäre das insgesamt immer noch O(N).

    Es werden aber nicht log(N) Schleifen durchlaufen, sondern N Schleifen.
    In der ersten Ebene läuft eine Schleife mit N Durchläufen.
    In der zweiten Ebene laufen zwei Schleifen mit je N/2 Durchläufen.
    In der dritten Ebene laufen vier Schleifen mit je N/4 Durchläufen.
    In der vierten Ebene laufen acht Schleifen mit je N/8 Durchläufen.
    usw.
    Insgesamt log(N) Ebenen, und in jeder Ebene laufen X Schleifen mit je Y Durchläufen, so dass X*Y==N.
    Also pro Ebene insgesamt N Schleifendurchläufe.
    Also für alle Ebenen insgesamt log(N)*N Schleifendurchläufe.

    Weil eben jede Ebene zwei "Instanzen" der darunterliegenden Ebene "spawnt".

    ps @Arcoth
    Ich bin mir sicher dass dir das klar ist, ich vermute nur dass Jester das gemeint hat. Weil so wie du es beschrieben hast klingt es eben nach "insgesamt log(N) Schleifen und pro Schleife immer 50% der Arbeit der Vorgänderschleife". Was eben O(N) wäre.

    EDIT: Copy+Paste Fehler korrigiert.



  • In der zweiten Ebene laufen zwei Schleifen mit je N/2 Durchläufen.

    Ah, da hab' ich zu einfach gedacht. Danke.



  • hustbaer schrieb:

    Es werden aber nicht log(N) Schleifen durchlaufen, sondern N Schleifen.

    Auch Unsinn von mir.
    Wie viele sind es denn jetzt wirklich?
    2*N - 1?
    (Bzw. N - 1 wenn man keine 1-Durchlauf Schleifen macht...)

    Naja, auf jeden Fall mehr als log(N) 😃



  • hustbaer schrieb:

    hustbaer schrieb:

    Es werden aber nicht log(N) Schleifen durchlaufen, sondern N Schleifen.

    Auch Unsinn von mir.

    Ich nahm an, du bezogst dich implizit auf O(n)\mathcal{O}(n), konkrete Angaben interessieren ITT ja nicht 😉

    Wie viele sind es denn jetzt wirklich?
    2*N - 1?
    (Bzw. N - 1 wenn man keine 1-Durchlauf Schleifen macht...)

    Sollte richtig sein, wenn man log(n)\log(n) Aufrufebenen hat: 2log(n)+11=2n12^{\log(n)+1}-1 = 2n-1.



  • Arcoth schrieb:

    hustbaer schrieb:

    hustbaer schrieb:

    Es werden aber nicht log(N) Schleifen durchlaufen, sondern N Schleifen.

    Auch Unsinn von mir.

    Ich nahm an, du bezogst dich implizit auf O(n)\mathcal{O}(n), konkrete Angaben interessieren ITT ja nicht 😉

    Stimmt auch wieder.
    Vor allem da es exakt sowieso nur stimmt wenn N zufällig ne Zweierpotenz ist.



  • Ja, genau das meinte ich, danke hustbaer. Die Anzahl der Schleifenist halt das eine, die Anzahl der jeweiligen Elemente das andere.

    Auf die Gefahr hin, dass ich mich wiederhole: Für rekursive Analysen würde ich stets die Methode mit den Rekurrenzen vorziehen. Insbesondere stehen einem dann ja mächtige Werkzeuge wie das Master-Theorem oder, wenn es der dicke Hammer sein muss, das Akra-Bazzi-Theorem zur Verfügung.



  • Hm, irgendwie hab ich das noch nicht vollständig verinnerlicht.
    Also der rekursive Aufruf mit der halben Liste als Parameter macht erstmal O(log(n)). In dieser Funktion kommen 2 for-schleife vor, die jeweils n/2, im zweiten Aufruf n/4, usw. durchlaufen. n/2,n/4,n/8 usw.. ergibt irgendwann etwa n zusammenadiert. Sodass dann O(log(n)*n) rauskommt? Und den zweiten rekuriven Aufruf auch mit O(log(n)*n) kann man dann weglassen, weil es eine Konstante ist, also log(n)*n + log(n)*n = O(log(n)*n)?

    Ich muss einen Algorithmus mit der Laufzeit O(log(n)*n) programmieren,
    worauf muss ich dann achten?



  • Mareike schrieb:

    Also der rekursive Aufruf mit der halben Liste als Parameter macht erstmal O(log(n)).

    Nein, das ist völliger quatsch, das kann so sein, muss es aber nicht. Und der Rest der Argumentation ist noch hahnebüchener. Zum Beispiel kann man den zweiten Aufruf eben nicht weglassen, weil es Konstanten sind. Wenn es nur ein Aufruf wäre, dann käme O(n) raus, und nur durch den zweiten wird n*log n draus, und wenn noch ein dritter Aufruf käme, dann käme wieder was anderes raus (siehe Master-Theorem).

    Beschäftige Dich mit dem Stoff und *verstehe* was da passiert. Momentan tust Du genau das nicht, sondern du versuchst eine Liste von Regeln zu finden, deren Abarbeitung die richtige Lösung liefert, ohne dass Du verstehen musst, inwiefern das die richtige Lösung ist. Du vermeidest damit das Lernen, ohne dafür ein schlechtes Gefühl haben zu müssen. -- clever... Oder auch nicht.


Anmelden zum Antworten