Zeitkomplexität (O-notation) < C/C++ < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:47 Di 28.02.2012 | | Autor: | lzaman |
| Aufgabe | Welche Zeitkomplexität (O-notation) hat das folgende Code-Fragment?
for (i = 0; i < n; i++)
{
j = 0;
while (j < n)
{
vector[i] = vector[i] + j;
j++;
}
} |
Hallo, könntet Ihr mir hier auf die Sprünge helfen, ich weiss überhaupt nicht, was ich hier machen soll. Für einen dicken Tipp wäre ich sehr dankbar...
Evtl. muss hier etwas mit [mm] n^2 [/mm] rauskommen, da ich zwei Schleifen habe, richtig?
|
|
| |
|
Hallo!
Prinzipiell mußt du dir anschaun, wir oft der innere teil mit dem Vektor aufgerufen wird.
In dem Fall hat die inner while-Schleife die gleiche Struktur wir die for-Schleife. Du könntest sie durch eine identsche For-Schleife ersetzen, allerdings mit nem j statt i.
Und damit erhöht sich die Anzahl der Durchläufe der Zeile mit dem Vektor exakt quadratisch.
|
|
|
|
