Theta Notation - Laufzeit eines kurzen Pseudo-Codes

  • Hallo! Ich bräuchte Eure Hilfe mit folgendem Pseudo Code. Ich verstehe grob, dass wenn Objekte mit allen anderen Objekten verglichen werden, wie hier, dass die Laufzeit dann O(n²) ist. Aber wie finde ich den average case heraus, und wie erkläre ich das?

    Vielen Dank schon im Vorraus!


    Code
    1. max = -∞
    2. for i = 1 to n-1 for j = i+1 to n if A[i] + A[j] > max then max = A[i] + A[j]
    3. return max

    Zeigen Sie, dass dieser Algorithmus Laufzeit Θ(n²) besitzt.

  • Hallo! Ich bräuchte Eure Hilfe mit folgendem Pseudo Code. Ich verstehe grob, dass wenn Objekte mit allen anderen Objekten verglichen werden, wie hier, dass die Laufzeit dann O(n²) ist. Aber wie finde ich den average case heraus, und wie erkläre ich das?

    Vielen Dank schon im Vorraus!


    Code
    1. max = -∞
    2. for i = 1 to n-1 for j = i+1 to n if A[i] + A[j] > max then max = A[i] + A[j]
    3. return max

    Zeigen Sie, dass dieser Algorithmus Laufzeit Θ(n²) besitzt.

    Hallo, du hast hier zwei verschachtelte Schleifen. Überlege dir am besten wie oft die innere Schleife in Abhängigkeit von n durchlaufen wird und wie oft die äußere Schleife.

    Vielleicht hilft es auch zuerst konkrete Werte für n einzusetzen und die Zwischenergebnisse anzuschreiben, um es besser abschätzen zu können. ;)

    "If you can dream it, you can do it."

    -- Walt Disney
    ʘ‿ʘ