Algorithmus Komplexität - Erklärung von O (log n)?

Question

Ich bin ziemlich neu zu Komplexität Maßnahmen, bitte ertragen mit.

Ich verstehe die folgende Komplexität Beispiele:

O (n) - Linear Time

Beispiel:

std::vector<int> MyV={1,4,6,2,9}; 
std::for_each(MyV.begin(), MyV.end(), [](int e1, int e1){return e1<e2;}); 
//I.e. n of operations based on the number of elements 

O (1) - Konstante Zeit

Beispiel:

for(int i=5; i--;) 
{ 
    //Do Stuff 
} 
//i.e. n of operations will be 5 

O (n2) - Quadratic Zeit

Beispiel:

std::vector<int> MyVec_A={1,2,3,4,5}; 
std::vector<int> MyVec_B={1,2,3}; 
for(int i=MyVec_A; i--;) 
{ 
    for(int x=MyVec_B; x--;) 
    { 
    //Do Stuff 
    } 
} 

Ist das obige Beispiel korrekt?

Wenn nicht, könnten Sie mir einige Hinweise geben, wie ich die Beispiele korrigieren kann?

Ich bin auch unsicher, Logarithmische Zeit O (log n), ein Beispiel wäre wirklich hilfreich?

Answer 1

Sie sagen, dass Ihr letztes Beispiel ist O (n), aber was ist n ??? Das solltest du dir selbst fragen. Normalerweise ist es die Größe des Vektors, in dem die Schleife ausgeführt wird.

würde der einfache Fall zu haben sein:

std::vector<int> MyVec_A = {1, 2, 3, 4, 5}; 
std::vector<int> MyVec_B = {1, 2, 3, 4, 5}; 
for(int i = MyVec_A; i--;) 
{ 
    for(int x = MyVec_B; x--;) 
    { 
    // Do Stuff that are of negligible complexity 
    } 
} 

und sagen jetzt zuversichtlich, die Komplexität dieses Beispiels ist: äquivalente O (n), wo n die Größe MyVec_A (oder MyVec_B).

Jetzt in Ihrem speziellen Beispiel die Länge der Vektoren unterscheiden, so müssen Sie ändern, was Sie haben. Lassen Sie uns sagen, dass MyVec_A Größe hat n und `` MyVec_B has size m`, dann wird diese doppelte Schleife eine Zeitkomplexität haben:

O (n * m)

Ich hoffe, es ist klar, dass, wenn die Vektoren haben die gleiche Größe, wie in meinem Beispiel, dann n = m und die Komplexität wird O (n * m) = O (n * n) = O (n).

---

Die Hallo Welt der logarithmischen Komplexität ist die binäre Suchmethode.

Bei einem Array von Ganzzahlen werden Sie aufgefordert, eine Zahl zu finden, die von Benutzereingaben stammt. Sie können entweder das gesamte Array linear durchsuchen (O (n) -Komplexität, wobei n die Größe des Arrays ist) oder, wenn das Array sortiert ist, können Sie das Element in O (logn) finden, indem Sie verwenden . Ich habe sogar ein Beispiel Binary Search (C++).

---

BTW, lernt eine einzige Frage zu stellen (oder sehr eng verbundene Teilfragen auf eine Frage).