Ausführen mit einer Laufzeit von O (n ^ 3 log n) mit 2 Schleifen [geschlossen] - c ++

Ich habe schon eine Weile versucht, das herauszufinden, und ich kann es einfach nicht verstehen. Jede Hilfe wäre großartig. Ich programmiere in C ++.

Finden Sie eine Laufzeit von O (n ^ 3 log n) mit zwei Schleifenstrukturen.

Antworten:

Angenommen, dies ist eine Hausaufgabe, hier ist ein Hinweis: Sie müssen ein setzen O(N*LogN) Operation innerhalb Ihrer zwei verschachtelten Schleifen, so dass die Operation keine Schleife benötigt.

Zum Beispiel können Sie mit einem Array von beginnen N Elemente, machen verschachtelte Schleifen an i und j dass Reverse-Array-Elemente zwischen i und j, und sortieren Sie dann das resultierende Array. Umkehr ist O(N)Sortierung ist O(N*LogN), so dominiert das Sortieren; Zwei äußere Schleifen liefern die restlichen O(N^2). Sowohl das Sortieren als auch das Umkehren kann unter Verwendung von Standardbibliotheksfunktionen ohne zusätzliche Schleifen erfolgen.

Es scheint fast jede Art von Komplexität mit wirklich nur einer Schleifenstruktur zu erreichen. In deinem Fall etwas wie (Pseudocode):

a := 0
b := 0
c := 0
d := 1
WHILE  a < n  OR  b < n  OR  c < n  OR  d < n  LOOP:
a := a + 1
IF  a = n  THEN:
a := 0
b := b + 1
IF  b = n  THEN:
b := 0
c := c + 1
IF  c = n  THEN:
c := 0
d := d * 2

Ich weiß, dass dies wahrscheinlich nicht das ist, was erforderlich ist, aber um nur einen Punkt zu machen - Sie können dies tun:

int x = 0;
for (int i=0; i<n; ++i) {
for (int j=0; j<n*n*log(n); ++j) {
x += j;
}
}