simple fragen zu laufzeiten

  • hey


    beim zweiten anlauf hab ich die laufzeitfunktionen immer noch nicht ganz durchschaut. asche auf mein haupt.


    wie auch immer, ich hätte zwei fragen.


    wird der durchlauf einer innere schleife immer um 1 iteriert, wie ist hier die laufzeit ?
    zb folgendes:
    Code:
    for(i=1; i<n+1; i++)
    {
    for(j=1; j<i; j++)
    {
    //do something
    }
    }

    die äußere schleife ist offensichtlich n *, und die innere? wie wird diese iteration in gesamtlaufzeit in theta(n) gewertet?


    zweite frage ist, wie ich eine laufzeit von n*wurzel(n) in form einer schleife darstellen kann.
    dabei mein ich NICHT etwa
    Code:
    for(i=0; i<n; i++)
    {
    for(j=0; j<wurzel(n); j++)
    {
    }
    }

    das ist mir zu einfach :p

  • Stell dir das ganze geometrisch vor.
    Schreib dir 2 Programme:


    for(i=1; i<n+1; i++)
    {
    for(j=1; j<i; j++)
    {
    System.out.print(x)
    }
    System.out.println()
    }


    for(i=1; i<n+1; i++)
    {
    for(j=1; j<n+1; j++)
    {
    if(j < i)
    System.out.print(x)
    else
    System.out.print(y)
    }
    System.out.println()
    }


    und vergleiche den Output für verschiedene Werte für n.

  • Eine kleine Anmerkung: Wenn Code-Stücke zwischen den Tags [ CODE] bzw. [ /CODE] platziert werden (ohne Abstand nach den öffnenden Klammern), bleibt deren Formatierung erhalten.


    Code
    1. for(i = 1; i < n+1; i++) {
    2. for(j = 1; j < i; j++) {
    3. //do something
    4. }
    5. }

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

    -- Walt Disney
    ʘ‿ʘ