Berechnung der Komplexität < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:13 So 03.05.2009 | | Autor: | farnold |
Ich tu mich momentan recht schwer wenn es darum geht die Laufzeitkomplexität T(n) eines Algorithmus anzugeben.
Ich will anhand eines Algorithmus die Laufzeitkomplexität berechnen. (Hab den Code erfunden, er wird also wenig sinn machen^^)
int testfunktion(a[],n)
{
for( int i = 1 ; i <= n ; i++)
{
if(i > 2)
{
a[i] = i;
}
}
}
1.)nun stellt sich mir die Frage welche Operation alle in die Laufzeitkomplexität T(n) einfließen:
- einer Variablen einen Wert zuweisen oder initialisiseren ?
- inkrementieren (siehe Variable einen Wert zuweisen) ?
- Vergleiche (z.B. a < b) ?
ich würde sagen alle 3 Operationen zählen dazu
2.) die if-anweisung innerhalb der schleife hat ja nichts mit "n" zutun, muss man diese dennoch in die Zeitkomplexität T(n) mit einbeziehen? ja, oder?
3.) ich will nun versuchen T(n) anzugeben
- for( int i = 1 ; i <= n ; i++) wäre das dann [mm] c_{1} [/mm] * (n+1) _oder_ c[1] * (n+1) + [mm] c_{2} [/mm] * n (es findet ja ein vergleich und eine inkrementierung statt?
usw.
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: (nicht 1 : 1)
http://www.uni-protokolle.de/foren/viewt/232864,0.html
Edit: sollte eigentlich unter die Kategorie "Hochschuel"
mfg fa
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:03 So 03.05.2009 | | Autor: | Gilga |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Laufzeitkomplexität wie asymptotisch angegeben, d.h. Konstanten sind irrelevant.
Man kann die LAufzeit untercshiedlich zählen.
z.B. nach TAktendann braucht eine Multiplikation mehr Takte als eine Addition.
EIne Speicherzuweisung z.B. 2 Tkakte ....
Sprüche kosten auch etwas....
Oder man sagt einfach alle elementaren Operationen kosten genau 1
if: Man nimmt den worstcase an .. also teuerster if-Zweig
for( int i = 1 ; i <= n ; i++)
{
if(i > 2)
{
a[i] = i;
}
}
}
== exakte Angabe: (deutlich einfacher als whileschleife betrachtet
int i=1
while(i<=n){
if(i > 2) a[i] = i;
i++;
}
Zuweisung + n*(Vergleich+Zuweisung+Inkrementierung)
Asymptotisch O(n)
Exakt: kommt darauf an wie teuer man die einzelnen Operationen macht
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:54 So 03.05.2009 | | Autor: | farnold |
also in der Vorlesung stellen wir zuerst T(n) mit der konstante c auf die "schwer zu bestimmen ist" deren genauer wert uns aber auch nicht weiter interessiert.
Erst wenn wir diese aufgestellt haben kümmern wir uns um die O- / Theta- was auch immer - Notation, diese ist für mich also ersteinmal "uninteressant"
hier ein auszug aus meinem mitschrieb :
void insertionsort(a[] , n)
{
int i, v, j;
for(i=1; i<=n ; i++) //c[1] * (n+1)
{
v=a[i]; j=i; //c[2] * n
while(a[j-1] > v) //c[3] * (Summe von 1 bis n) (t[i])
{
a[j] = a[j-1]; j--; //c[4] * (Summe von 1 bis n) (t[i] - 1)
}
a[j] = v; //c[5] * n
}
}
mir ist nur die gewichtung der einzelnen Operationen ein Rätsel.
=>for(i=1; i<=n ; i++) ist c_[1] * (n+1) (laut Mitschrieb)
|| in meinen Augen wäre dies aber c[1] * (n+1) (für die Vergleiche für (i<=n)) + c[2] * n ( für das inkrementieren)
=>v=a[i]; j=i; ist c_[2] * n (laut mitschrieb)
|| in meinen AUgen wäre dies aber c_[2]*n (für Zuweisung der ersten Variable) + c_[3] * n (für Zuweisung der zweiten Variable)
ich glaube meine betrachtung von T(n) würde deinem Beispiel, das mir wesentlich logischer erscheint, näher kommen als unserem aufschrieb.
Klar ist es dann für O-Notation egal ob da "c_[2] * n" oder "c_[2] * n + c_[3] * n" steht, aber was ist nun korrekt/sauberer für T(n).
ist mein Denken hier falsch oder geht meine "Bestimmung" von T(n) auch? Bzw. ich verstehe die Gewichtung der Kosten in unsrem aufschrieb nicht.
mfg fa
Edit:
>int i=1
>while(i<=n){
> if(i > 2) a[i] = i;
>i++;
>}
>
>Zuweisung + n*(Vergleich+Zuweisung+Inkrementierung)
lässt man hier die n - Vergleiche in der if-anweisung weg oder kann man auch Zuweisung + n*(Vergleich1+Vergleich2+Zuweisung+Inkrementierung)
schreiben?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:53 Mo 04.05.2009 | | Autor: | Gilga |
>lässt man hier die n - Vergleiche in der if-anweisung weg oder kann man auch Zuweisung
Sorry vergessen. Muss man auch beachten.
Man kann den Mitschrieb auch als vereinfachung sehen
c1*(n+1)+c2*n=(c1+c2)*n+c1 < c*n+c=(n+1)*c für passendes c
Deine Berechnung stimmt natürlich auch.
>aber was ist nun korrekt/sauberer für T(n)
korrekt: Muss man festlegen (wie teuer Operationen...)
sauber: ausführlicher ist i.A. besser.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:41 Mo 04.05.2009 | | Autor: | farnold |
Hallo,
vielen dank für die Hilfe :)
eine letzte frage hätte ich noch, um letzte unklarheiten zu beseitigen :(
1 int a[N];
2 a[0] = ........;
3 for( int i = 0 ; i < N-1 ; i++ )
4 {
5 int smallest = i;
6 for(int j = i+1 ; j < N ; j++)
7 {
8 if(a[j] < a [smallest]
9 {smallest = j; }
10 }
11 std::swap(a[j],a[smallest])
12 }
wir haben T(N) wiefolgt aufgestellt:
T(N) = c(N-1) + 1*d + T(N-1)
- woher kommt das 1*d?
- warum wurde die funktion swap(...) und die zuweisungen komplett unter den tisch fallen gelassen?
- genügt es sich bei sortieralgorithmen nur auf die Schleifen zu beschränken? Was darf ich um T(N) aufzustellen weglassen? Ich sehe da irgendwie kein System wie wir es in unserer Vorlesung machen, einmal zählen Zuweisungen, dann werden sie wieder komplett irgnoriert !?
würde mein T(N) auch stimmen? ( for(...) behandle ich bei jedem durchlauf als 1ne Operation, genau wie die fkt. swap(...) ) :
T(N) = [mm] c_{1} [/mm] * N (Z.2) + [mm] c_{2} [/mm] * (N-1) (Z.3) + [mm] c_{3} [/mm] * (N-2) (Z.5) + [mm] c_{4} [/mm] * T(N-1) (Z.6-10) + [mm] c_{5} [/mm] * (N-2) (Z.11) ? und dann weiterrechnen
mfg fa
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:19 Mo 04.05.2009 | | Autor: | Gilga |
1*d
keine Ahnung. entweder fehlen zu dieser Aufageb noch irgendwelche Angaben oder die Vorlesung ist recht konfus.
Vielleicht soll es ein konstanter Aufwand sein. (z.B. swap)
swap:
entspricht 3 zuweisungen
tmp=a[i]
a[i]=a[smallest]
a[smallest]=tmp
Die rekursive Darstellung sieht T(N) als N Schleifendurchläufe der for-Schleife aus Zeile 3
c(N-1) = Arbeit innerhalb eines Schleifendurchlaufs //Zeile 6-10
T(N-1) Arbeit der restlichen Schleifendurchläufe.
das ist die Idee der Rekursion: Arbeit in diesem Durchlauf+Arbeit der restlichen Durchläufe
(Um Rekursion zu verstehen muss man Rekursion verstehen ;)
würde mein T(N) auch stimmen? Nein
z.B. durch rekursion würde N * c5*(N-2) Kosten für Zeile 11 entstehen
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:50 Mo 04.05.2009 | | Autor: | farnold |
Hi,
danke für die schnelle Anwort :)
> z.B. durch rekursion würde N * c5*(N-2) Kosten für Zeile 11
warum N * c5*(N-2) für Zeile 11? Zeile 11 befindet sich ja nur in der äußeren Schleife die wegen "i < N-1" nur N-2 mal eintreten kann => c[5] * (N-2) * 3
(*3 weil ja swap 3 Opearationen jeweils kostet), oder nicht?
Edit: axo die kosten für einen Schleifendurchlauf sind also c[5]*3 ^^
und für alle durchläufe ist sie am ende (c[5]*3)*(N-2))? weil es tritt ja rekursiv N-2 mal ein?
> Die rekursive Darstellung sieht T(N) als N Schleifendurchläufe der > for-Schleife aus Zeile 3
> c(N-1) = Arbeit innerhalb eines Schleifendurchlaufs //Zeile 6-10
warum nur c(N-1) für einen (äußeren?) Schleifendurchlauf ? bzw. wie kommt ihr auf c(N-1)
für mich sehen die Kosten für einen äußerer Schleifendurchlauf wiefolgt aus:
1- muss man da nicht die "i+1 bis N-1" durchläufe der inneren Schleife, in welcher selbst nochmal Operationen ausgeführt werden?
2- der eine aufruf der swap Funktion
3- die eine Zuweisung
4- die eine Überprüfung der äußeren for-Schleife
und das ergibt was anderes als c(N-1)
dann komm "rekursiv?" der 2. aufruf der äußeren Schleife, die Operationen bleiben gleich, bis auf die innere Schleife die nun einmal weniger aufgerufen wird....
wo liegt mein denkfehler? :(
> T(N-1) Arbeit der restlichen Schleifendurchläufe.
steht T(N-1) also für die restlichen N-2 äußeren SChleifendurchläufe, wobei ein äußerer Durchlauf die inneren SChleifendurchläufe jeweils beinhaltet?
/*
Rekursion sagt mir schon etwas, für mich war Rekrusion bisher immer so:
ich habe eine Funktion und in dieser Funktion rufe ich "rekursiv" dieselbe Funktion erneut auf ( wahrscheinlich aber mit anderen Parametern, damit sie termieren kann)
*/
-kurz gefragt, wie komme ich auf c(N-1) für einen Durchlauf?
was ja ne schöne zahl ist, da man am ende der rekursion auf den kleinen gauß trifft^^
-das N steht ja -einfach ausgedrückt - für die Anzahl der Operationen?
mfg fa
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:26 Mo 04.05.2009 | | Autor: | Gilga |
N * c5*(N-2) für Zeile 11?
gegenbeispiel für deine rechnung....
T(N)=T(N-1)+.....+....c5*(N-2)
=T(N-2)+....+c5*(N-3)+....+c5*(N-3)
Durch die rekursion komtm N * c5*(N-2) raus. was NICHt stimmt
Edit: axo die kosten für einen Schleifendurchlauf sind also c[5]*3 ^^
und für alle durchläufe ist sie am ende (c[5]*3)*(N-2))? weil es tritt ja rekursiv N-2 mal ein?
Jein. Dies wären nur di ekosten von Zeile 11 die innere Schleife ist ja von N abhängig
Wobei dann c5 einfach der Aufwand je Zuweisung ist.
warum nur c(N-1) für einen (äußeren?) Schleifendurchlauf ?
innere Schleife
for(int j = i+1 ; j < N ; j++)
1. Durchlauf der äußeren for(int j = 1 ; j < N ; j++) kosten (N-1)*c
2. for(int j = 2 ; j < N ; j++) kosten (N-2)*c
......
1- muss man da nicht die "i+1 bis N-1" durchläufe der inneren Schleife, in welcher selbst nochmal Operationen ausgeführt werden?
2- der eine aufruf der swap Funktion
3- die eine Zuweisung
4- die eine Überprüfung der äußeren for-Schleife
c1*(N-1)+3*c2+1+1 = c1*(N-1)+konstante
die schätze ich entweder ab und verstekce sie in c1 oder
ich schreibe c+(N-1)+d
:)
vermutlich soll d diese Operationen ausdrücken
steht T(N-1) also für die restlichen N-2 äußeren SChleifendurchläufe, wobei ein äußerer Durchlauf die inneren SChleifendurchläufe jeweils beinhaltet?
Ja
-das N steht ja -einfach ausgedrückt - für die Anzahl der Operationen?
NEIN. N ist die Feldgröße der zu sotierenden Zahlen
Man gibt Komplexität immer in abhängigkeit der Eingabengröße an
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:12 Mo 04.05.2009 | | Autor: | farnold |
super, so langsam kommt doch licht ins dunkle :)
das heißt, wenn ich so einen quellcode sehe, kann ich ruhig ersteinmal alle kosten für jede Operation in mein T(N) packen und den unnötigen kram pack ich schön in eine konstante^^
unsere innere Schleife seinerseits führt ja nun auch noch 2 zusätzliche Operationen aus, die wir bisher außer acht gelassen haben (jeweils einen Vergleich und eine Zuweisung)
=> 1. Schleifendurchlauf (ausführlich) : c1*(N-1) + c3*(N-2) + c4(N-2) +3*c2+1+1 wie bekomme ich das in folgende Form: c1*(N-1)+konstante?
nochmals danke, dass mit dem aufstellen von T(n) und Rekursion hätte ich ohne deine Hilfe wohl nie verstanden :)
mfg fa
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:31 Mo 04.05.2009 | | Autor: | Gilga |
for( int i = 0 ; i < N-1 ; i++ )
4 {
5 int smallest = i;
6 for(int j = i+1 ; j < N ; j++)
7 {
8 if(a[j] < a [smallest]
9 {smallest = j; }
10 }
11 std::swap(a[j],a[smallest])
12 }
1. Schleifendurchlauf (ausführlich) : c1*(N-1) + c3*(N-2) + c4(N-2) +3*c2+1+1
???????
wo kommen denn die ganzen Ns her?
i=0 im 1. Durchlauf
=>
for(int j = 1 ; j < N ; j++)
7 {
8 if(a[j] < a [smallest]
9 {smallest = j; }
10 }
(N-1) Schleifendurchläufe der Zeilen 8 und 9 mit Kosten c
also (N-1)*c
+ Zeile 5 und 11 =(konstante Kosten unab. von N)!
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 21:59 Mo 04.05.2009 | | Autor: | farnold |
> 6for(int j = 1 ; j < N ; j++)
> 7 {
> 8 if(a[j] < a [smallest]
> 9 {smallest = j; }
> 10 }
>
> (N-1) Schleifendurchläufe der Zeilen 8 und 9 mit Kosten c
> also (N-1)*c
also das "ausführliche T(N) kommt bei mir sozustande:
für den 1. äußeren Schleifendurchlauft gilt für die innere Schleife:
c(N-1) kosten für Zeile 6
c(N-2) kosten für Zeile 8 // eins weniger da er bei false ja nicht mehr reingeht
c(N-2) kosten für Zeile 9 // hier dasselbe
=> c(N-1) + c(N-2) + c(N-2) // kosten der inneren Schleife beim ersten durchlauf,
aber [mm] c_{1}(N-1) [/mm] + [mm] c_{2}(N-2) [/mm] + [mm] c_{3}(N-2) [/mm] ist ja nicht gleich c(N-1), was hab ich falsch gemacht/gedacht
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Mi 06.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
