Programm Laufzeit und Speicherbedarf O-Notation

[sh33p]

Folgendes Programm habe ich aus einem doofen Pseudcode in Java transferiert:

import java.util.*;
public class Dummesprogramm {

  public static void main(String[] args) {
  
  Scanner scan = new Scanner(System.in);
  System.out.println("Bitte n eingeben");
  int n = scan.nextInt();
  
    int k = 0;

    int m =n;
    
    while(m != 0){
      if(m %2 == 0){
        m = m/2;
      } else{
      k = k+1;
      m = (m-1)/2;

      }
      System.out.println("m = "+ m);
      System.out.println("n = "+ n);
      System.out.println("k = "+ k);
      System.out.println(" ");
    }
    
  }
}

Man soll den Speicher und Laufzeitbedarf angeben, wenn n die Problemgröße darstellt.
Meine Idee dazu:

Ich denke die Laufzeit ist hier O(n), da die Schleife n mal durchlaufen wird.

Wäre m die Problemgröße,dann wäre der Laufzeitbedarf (2*ldn),da die Schleife bei jedem 2. Durchlauf die eingegebenen Daten halbiert, sprich in der O-Notation O(log n).

Wie sieht es mit dem Speicherbedarf aus?Wie ermittel ich diesen?

 

[XHelp]

Also ich würde glatt vermuten, dass die Laufzeit O( log(n) ) ist, da du ja immer durch 2 teilst.
Halbiert wird übrigens in jedem Schritt.
Laut Zeile 13 wäre die Laufzeit auch O( log(m) )

Speicherbedarf ist eine recht kreatieve Sache... da müsste man doch den echten Pseudocode sehen (wie man z.b. die Eingabe macht). Aber ich denke das ist nur auf die integers bezogen... die sind (idR) 32 bit lang. aber generell kommt da ja noch Prozesskontrollblock, das Programm an sich etc. dazu, deswegen kannst du, meiner Meinung nach, über Speicherbedarf keine wirklich schlaue aussage treffen.

 

[sh33p]

nochmal zur Laufzeit..wie kann die Laufzeit O(logn) sein,wenn die Problemgröße n darstellt?mit n passiert ja nichts.wenn n z.b 13 is,bleibt n immer 13.

anders bei m, m wird immer geteilt,daher logn

 

[XHelp]

[JAVA=13]int m =n;[/code]
n ist ja deine Eingabe und die Laufzeit hängt von der Eingabe ab.

Anders gesagt: welche Zahl musst du denn Verändern, um eine andere Laufzeit zu bekommen? n. Deswegen ist ja auch die Laufzeit von n abhängig

 

[sh33p]

ok alles klar danke

 

[sh33p]

noch ne Frage..wenn das Programm keine Eingabe hat und n als normale variable deklariere,dann ist doch die laufzeit immer noch von n abhängig oder? weil desto größer n ist desto länger ist die laufzeit

 

[XHelp]

Sry, habe die Frage erst jetzt bemerkt.
Ne, von n hängt es dann nicht ab in dem Sinne. Die Landau Notation untersucht ja die Funktionen in Abhängigkeit von Eingangsvariablen. Da du keine hast würde ich glatt mal vermuten, dass es Theta(1) ist.