[HaBo]

Dawen · 16.05.05, 00:12

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 !!

blueflash · 16.05.05, 12:07

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.

Anzeige

- Anzeige -

Dawen · 16.05.05, 12:16

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 ?

blueflash · 16.05.05, 14:28

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.

Mat_the_Mad · 17.05.05, 15:36

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.

Anzeige

- Anzeige -

16.05.05, 00:12	#1 (permalink)
Dawen Registriert seit: 19.08.04 Likes: 1	Laufzeitanalyse bei Algorithmen Anzeige 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 !!

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Zukunftsträchtige Algorithmen...	enkore	Cryptography & Encryption	9	09.08.09 21:17
Algorithmen	cr4ven	Code Kitchen	4	28.10.08 20:35
Algorithmen für die SAM	subzeroo	Cryptography & Encryption	20	24.10.05 18:17
Algorithmen für WPA	Elderan	Cryptography & Encryption	4	23.10.05 20:13
Datenstrukturen und Algorithmen	Dawen	Code Kitchen	0	14.04.05 23:05

16.05.05, 12:07	#2 (permalink)
blueflash Member of Honour Registriert seit: 03.10.01 Likes: 1	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.

16.05.05, 12:16	#3 (permalink)
Dawen Themenstarter Registriert seit: 19.08.04 Likes: 1	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 ?

16.05.05, 14:28	#4 (permalink)
blueflash Member of Honour Registriert seit: 03.10.01 Likes: 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.

17.05.05, 15:36	#5 (permalink)
Mat_the_Mad Registriert seit: 29.01.05 Likes: 0	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.

[HaBo]

Laufzeitanalyse bei Algorithmen