O-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:49 Sa 14.02.2009 | | Autor: | bonanza |
| Aufgabe | Ermitteln Sie die Komplexität von Bubblesort in der O-Notation:
void bubbleSort(int numbers[], int array_size)
{
int i, j, temp;
for (i = (array_size - 1); i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (numbers[j-1] > numbers[j])
{
temp = numbers[j-1];
numbers[j-1] = numbers[j];
numbers[j] = temp;
}
}
}
}
|
Hi,
ich habe eine eher generelle Frage zur Laufzeitanalyse von Funktionen. Undzwar ist mir nicht wirklich klar, wie die Laufzeiten der inneren und äußeren Schleifen zu einander stehen.
ich weiß, dass die äußere Schleifen N-1 Iterationen hat, und die innere Schleife zuerst N-1, dann N-2, N-3, ... Iterationen und die Laufzeit der If-Verzweigung 3 Operationen hat und damit O(1) entspricht. Aber wie muss ich die jetzt zusammen in verbindung setzen um die GEsamtlaufzeit zu erhalten?
Muss ich die Iterationen der äußeren mit denen der inneren multiplizieren?
(N-1)*(N*(N-1)/2+3)
oder werden die "nur" addiert ?
(N-1)+(N*(N-1)/2+3)
Eine kleiner Erläuterung wäre sehr hilfreich :)
danke schonmal im voraus!
|
|
| |
|
Hallo bonanza,
Im Worst-Case (z.B. beim Feld 3,2,1) ist die if-Abfrage bei jedem Durchlauf der inneren for-Schleife erfüllt. Dann führt die innere Schleife genau [mm]i\![/mm] Schritte aus, da [mm]j=1,\dotsc,i\![/mm]. Im Fall [mm]i = 0\![/mm] wird nur der innere Schleifenkopf ausgeführt, wofür wir einfach mal den Verbrauch einer Zeiteinheit annehmen. Die if-Abfrage und die 3 Befehle im if-Körper sollen jetzt mal insg. 4 Zeiteinheiten verbrauchen. Dann hätte man also insg. array_size-1 Schritte, wo die innere for-Schleife jeweils i-mal ausgeführt wird und einen array_size'ten Schritt, wo nur der innere Schleifenkopf ausgeführt wird. Die Anzahl Schritte insg. ist damit:
[mm]1+\sum_{i=1}^{\operatorname{array\_size}-1}{\sum_{j=1}^i{4}}[/mm]
Diese verschachtelte Summe mußt du jetzt von innen nach außen auflösen (z.B. mit den Formeln von Gauss) und danach schauen, welche Laufzeit sich durch die O-Notation ergibt.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:01 Sa 14.02.2009 | | Autor: | bonanza |
| Aufgabe | Geben Sie mit Hilfe der O-Notation die Laufzeiten der beiden Funktionen an:
int Pow1(int n)
{
if (n > 0) {
return (2*Pow1(n-1));
}
else {
return 1;
}
}
//-----------
int Pow2(int n)
{
if (n > 0) {
return (Pow2(n-1) + Pow2(n-1));
}
else {
return 1;
}
} |
Danke für deine Antwort!
Wären das dann
[mm] 2*(Arraysize)^2-Arraysize+1 [/mm] = [mm] O(Arraysize^2) [/mm] ?
Ich habe jetzt direkt noch eine Frage... Wie geht bei bei der Analyse rekursiver Funktionen vor ?
Ich hätte jetzt gesagt, dass die Funktion "Pow1"
1 + 1*n schritte macht und dann eine Laufzeit von O(n) hätte.
bei Funktion "Pow2" bin ich mir wiederrum nicht sicher ob es O(2n) = O(n) oder [mm] O(n^2) [/mm] ist.
Wäre auch hier für eine Erläuterung wieder dankbar ;)
|
|
|
| |
|
Hallo bonanza,
> Geben Sie mit Hilfe der O-Notation die Laufzeiten der
> beiden Funktionen an:
>
> int Pow1(int n)
> {
> if (n > 0) {
> return (2*Pow1(n-1));
> }
> else {
> return 1;
> }
> }
>
> //-----------
>
> int Pow2(int n)
> {
> if (n > 0) {
> return (Pow2(n-1) + Pow2(n-1));
> }
> else {
> return 1;
> }
> }
> Danke für deine Antwort!
>
> Wären das dann
> [mm]2*(Arraysize)^2-Arraysize+1[/mm] = [mm]O(Arraysize^2)[/mm] ?
Fast, du hast eine 2 beim arraysize vergessen.
> Ich habe jetzt direkt noch eine Frage... Wie geht bei bei
> der Analyse rekursiver Funktionen vor ?
Du mußt die Anzahl der Aufrufe der Funktion zählen bis eine (der) Abbruchbedingung(en) der Funktion erreicht ist.
Gibt es keine Abbruchbedingungen ist die Laufzeit der Funktion durch die, an die Funktion zugewiesene, Stackgröße begrenzt.
> Ich hätte jetzt gesagt, dass die Funktion "Pow1"
> 1 + 1*n schritte macht und dann eine Laufzeit von O(n)
> hätte.
Es ist sicherlich in O(n). Für n = 0, werden 2 Z.E. (if-Abfrage, return 1) verwendet. Für n = 1 wird erstmal 1 Z.E. mehr verwendet (if-Abfrage) und dann findet der Aufruf Pow1(0) statt, der 2 Z.E. benötigt, die anschließende Multiplikation mit Rückgabe soll jetzt mal 1 Z.E. benötigen. Insgesamt also: 1 + 2 + 1 = 4 = 2*2 Z.E. . Für n = 2 benötigt man bereits 2(if-Abfrage, return mit mult.) + Schritte für Pow1(1) = 2+4 = 6 = 2*3 Z.E. .
Behauptung: Für Pow1(n) benötigt man 2(n+1) Zeiteinheiten.
Beweis durch Induktion:
n = 0 klar. n -> n+1: Nach Induktionsannahme benötigt man für Pow1(n+1) 2(if-Abfrage, return mit mult.) + 2(n+1) Z.E. = 2(1+n+1) Z.E. = 2((n+1)+1) Z.E. qed
> bei Funktion "Pow2" bin ich mir wiederrum nicht sicher ob
> es O(2n) = O(n) oder [mm]O(n^2)[/mm] ist.
Pow2(0) : [mm]2\texttt{ ZE} = 2^1\texttt{ ZE}[/mm]
Pow2(1) : [mm]2^1\texttt{(if,+)} + 2^1 + 2^1\texttt{ ZE}=2^1+2^2\texttt{ ZE}[/mm]
Pow2(2) : [mm]2 + 2+2^2 + 2+2^2\texttt{ ZE}=2^1+2^2+2^3\texttt{ ZE}[/mm]
Pow2(3) : [mm]2^1 + 2^2 + 2^3 + 2^4\texttt{ ZE}[/mm]
Pow2(4) : [mm]2^1 + 2^2 + 2^3 + 2^4 + 2^5\texttt{ ZE}[/mm]
Vermutung: Pow2(n) : [mm]\textstyle\sum_{i=1}^{n+1}{2^i}\texttt{ ZE}[/mm].
Siehe dir nun die ![[]](/images/popup.gif) geometrische Reihe an, um die Summe zu vereinfachen. Danach mußt du die Formel mit vollständiger Induktion beweisen.
Gruß V.N.
|
|
|
|
