Laufzeitanalyse bei Algorithmen

D

Dawen

0
Servus,

ich habe schon gesucht und gefragt aber irgendwie hat da keienr so richtig Ahnung von. Ich beschäftige mich mit Algortihmen und der Laufzeitanalyse. Habe aber noch einige verständnis Programme und zwar :

T(n) = 695n? + 397n + 6148 = O(n?) , wird dabei immer vom höchsten Wert ausgegangen, also beispielsweise T(n) = 1000n? + 695n? + 397n + 6148 = O(n?) ?

Code: 
int[] a = new int[n];
      int[] b = new int[n];
      int   i = 0;
      while( i != n){
         a[i] = 0;
         i    = i+1;
      }
      i = 0;
      while( i != n){
         b[i] = 0;
         i    = i + 1;
      }

Ein Freund hat schon in anderen Boards gefragt und bis jetzt keine Antwort bekommen. Der Prof meint folgendes :

f(n) = (2n+1+)+(2n+1)
f(n) = 4n+2
f(n) = O(n)

Müsste es aber nicht so richtig sein :

( n + 1 + 1 ) " n für die Schleife und zweimal das + 1 wegen dem Vergleich und der Inkrementierung " + 1 " Die 1 wegen der Zuweisung von i + 1 " + ( n + 1 + 1) "Wieder n für die Schleifen und zweimal +1 wegen dem Vergleich und der Inkrementierung "

Also :

f(n) = (n+1+1+1)+1+(n+1+1)
f(n) = 2n + 5
f(n) = 2n

Allgmein paar Tippe und ähnliches wäre auch nicht schlecht, weil irgendwie will das nicht in emeine Birne. Danke euch !!
 
Wichtig ist, dass du feststellst, dass in beiden Schleifen n-mal eine konstante Anzahl von Anweisungen durchgeführt wird. Also zB nC1 + nC2 damit kommst du dann auf A(n)=nC3=O(n)


Achja: Es gilt A(f) = O(g), wenn lim ( f / g ) = 0, also g schneller wächst als f.
 
Ich bin ja erstmal Froh das mir einer antwortet, danke dir erstmal.

Es wird eine konstante Anzahl durchgeführt, da ja beide Schleifen die gleichen Anweisungen ausführen. Somit wäre also O(n) richtig und nicht wie ich meinte O(n?), da dies ja in verschachtelten Schleifen der Fall wäre. Aber wie genau kommt man auf 2n+1 ?
 
die 2 bedeuten die beiden zuweisungsanweisungen ( = ) in den schleifen.
die 1 steht für die initialisierung von i.

offenbar hat dein prof. nur die zuweisungsoperationen gezählt. man könnte auch jede addition usw. mitzählen, dies ist aber relativ egal, wichtig ist, das O(n) rauskommt.
 
Du solltest du dich durch die "O()" -Schreibweise nicht verwirren lassen. Denn sie gibt nur über den "worst-case" Auskunft. O(n) heisst, dass die Anzahl Operationen/Schleifendurchläufe für grosse n (gegen unendlich) proportional zu n ist. Dein "Algorithmus" T(n) = 695n? + 397n + 6148 hat O(n?), weil er für grosse n prop. zu n? ist (die kleineren Potenzen sind für grosse n vernachlässigbar).

Hoffe, hat dir geholfen.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben