Laufzeit bestimmen



  • @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