Laufzeit eines Algorithmus bestimmen

pac89

Hallo, ich weiß nicht wie ich die Laufzeit vom folgenden algorithmus bestimmen kann kann. der code lautet:

(int, int) divInter (int n, int k){
2 int q=0;
3 int r=n;
4 int m=2*k;
5 while (r>=m){
6 q=q+1;
7 r=r-m;
8 }
9 q=q*2;
10 return (q,r);
11 }

die lösung davon lautet: w(n,k) = n/2 *5 +7

wobei das n/2 abgerundet wird.

kann mir jmd. erklären, wie man vorgeht? ich möchte das lernen, aber weiß nicht wie man solche aufgaben "anpackt".

volkard

Wenn ich umschreibe zu

(int, int) divInter (int n, int k){
  int q=0;               //1
  int r=n;               //1
  int m=2*k;             //1 (2?)
nochmal:
  bool test=(r<m);       //1  //Die Schleife läuft n/k mal
  if test goto fertig;   //1
    q=q+1;               //1
    r=r-m;               //1
  goto nochmal           //1
fertig:
  q=q*2;                 //1
  return (q,r);          //1 (2?)
}

komme ich auf w(n,k) = n/k *5 + 5
Schon recht dicht dran.
Man müßte wissen, welche Anweisungen in diesem Spiel welche Kosten haben.
Das sollte im Skript zur Vorlesung spezifiziert sein.

pac89

es wurde gesagt, dass Grundrechenarten, Vergleiche und Zuweisungen in exakt einer Zeiteinheit ausgeführt werden.

edit: also muss ich nur die anzahl der operationen + kosten zählen, oder wie?

volkard

pac89 schrieb:

es wurde gesagt, dass Grundrechenarten, Vergleiche und Zuweisungen in exakt einer Zeiteinheit ausgeführt werden.

Oki.

(int, int) divInter (int n, int k){
  int q=0;        //Z 1
  int r=n;        //Z 1
  int m=2*k;      //ZG 2
  while (r>=m){   //V 1   //Schleife läuft n/k mal
    q=q+1;        //ZG 2
    r=r-m;        //ZG 2
  }
  q=q*2;          //ZG 2
  return (q,r);   //?
}

Macht w(n,k)=n/k*5+6+?
Vielleicht zählt das return als eine Zuweisung? Mußt Du rausfinden, wenn DU noch ein paar Beispiele mit Lösung hast, kannste ganz leicht isolieren, wie der Prof genau zählt.

edit: also muss ich nur die anzahl der operationen + kosten zählen, oder wie?

Ganz genau.

pac89

okay, vielen dank für die hilfe. bei den anderen beispielen schlag ich mich dann selber mal durch.