int n;
int i, j, k = 0;
for (i = n/2; i <= n; i++) {
for (j = 2; j <= n; j = j * 2) {
k = k + n/2;
}
}
Nur müssen die Zeitkomplexität der Code-Snippets und die Antwort ist Θ (n log n) berechnen, aber können Sie erklären, wie es ist Θ (n log n)Wie ist die zeitliche Komplexität des Codes Θ (nLogn)?
Es ist wirklich nicht so schwierig.
Die äußere Schleife läuft n/2 mal. Das ist O(n) Komplexität.
Die innere Schleife hängt wieder nur von n ab. Es hängt nicht von der i aus der ersten Schleife ab. Für die Komplexität der inneren Schleife können wir die äußere Schleife vollständig ignorieren. Welch ein Glück!. j Multiples jedes Mal von 2 so haben wir logarithm base 2. Das ist O(log(n)).
Die Schleifen sind verschachtelt, so multiplizieren wir, also mit der Endung:
O(n log(n))
So haben Sie alle Infos. Warum kannst du nicht rechnen? –
Ihr Hinweis ist, es ist nicht O (n!) Aber ernsthaft, wenn Sie es nicht durch Prüfung herausfinden können, legen Sie einige printf Aufrufe dort zu verfolgen, wie oft es heißt und sehen, wenn Sie das Muster nicht selbst finden, wie Sie die ändern Schleifengröße? –
"... kannst du erklären, wie es ist Θ (nLogn)" - kannst du erklären, wie es alles sein könnte * aber * Θ (nLogn)? – WhozCraig