Verständnis von Big O

Question

Angesichts der folgenden Code, was ist die Komplexität von 3. und wie würde ich einfache Algorithmen mit den folgenden Komplexitäten darstellen?

O (n² + n)
O (n² + 2n)
O (logn) O (n log n)

var collection = new[] {1,2,3}; 
var collection2 = new[] {1,2,3}; 

//1. 
//On 
foreach(var i in c1) 
{ 
} 

//2. 
//On² 
foreach(var i in c1) 
{ 
    foreach(var j in c1) 
    { 
    } 
} 

//3. 
//O(nⁿ⁺ᵒ)? 
foreach(var i in c1) 
{ 
    foreach(var j in c2) 
    { 
    } 
} 

Answer 1

Die äußere foreach wird ausgeführt n = | c1 | Zeiten (wobei | x | die Größe von c1 ist), während der innere foreach m = | ausgeführt wird c2 | mal. Das ist O (n * m) mal insgesamt.

---

wie würde ich vertrete einfache Algorithmen mit folgenden Komplexität?

• O (n² + n)

Dies ist das gleiche wie O (n^2). Etwas, das O (n^2) Zeit braucht, wäre ein Toast mit jeder anderen Person auf einer Party, unter der Annahme, dass immer genau zwei Personen auf einen Toast anstoßen und nur eine Person gleichzeitig röstet.

• O (n² + 2n)

Gleiche wie oben ist; der O (n^2) -Term dominiert. Ein anderes Beispiel für eine O (n^2) -Aufgabe ist das Pflanzen von Bäumen in einem quadratischen Garten der Länge n, vorausgesetzt, dass es dauernd dauert, um jeden Baum zu pflanzen, und dass, sobald Sie einen Baum pflanzen, andere Bäume aus seiner Umgebung ausgeschlossen sind.

• O (log n)

Ein Beispiel hierfür wäre ein Wort in einem Wörterbuch werden finden, indem sie wiederholt den Mittelpunkt der Region von Seiten Kommissionierung Sie neben suchen müssen. (Mit anderen Worten, eine binäre Suche.)

• O (n log n)

Verwenden Sie den obigen Algorithmus, aber jetzt haben Sie jedes Wort im Wörterbuch zu finden.

Answer 2

3 ist O (n * m) oder O (n^2) wenn die beiden Sammlungen die gleiche Größe haben.

O (n^2 + n) ist sinnlos, weil n kleiner ist als n^2. Schreib einfach O (n^2).

Die meisten brauchbaren comparison sort Algorithmen laufen bei O (n * log (n)). Wenn Sie keine wissen, schauen Sie auf Wikipedia.

Ein binary search ist O (log (n)).

Answer 3

Die Komplexität von 3 ist O (m * n). Es gibt keine Komplexität O (n + n) oder O (n + 2n).Es ist nur O (n). Dies liegt daran, dass n 0 ist (n).

Beispiel für O (log (n)) ist binäre Suche.

Beispiel für O (n * log (n)) ist merge sort.

Answer 4

Es gibt kein O (n² + n) oder O (n^2 + 2n). Abgesehen von den meisten mathematischen Grundlagen der algorithmischen Komplexität müssen Sie zumindest wissen, dass es "aymptotisch" ist. Wenn N gegen die Unendlichkeit geht, wird der Wert von n^2 + n durch den Ausdruck n^2 dominiert, also ist das die asymptotische Komplexität von n^2 + n.

Die Komplexität von 3 ist O (I * J), wobei I und J die Größe der Eingaben in c1 und c2 sind.

Answer 5

Die Wahrheit zu sagen O (n² + n) & O (n² + 2n) sind gleich.