algorithme - Qu'est-ce qu'une explication anglaise simple de la notation "Big O"

100

actualAlgorithmTime(N) ∈ O(bound(N))                                        e.g. "time to mergesort N elements                                               is O(N log(N))" 

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       " ────────────────────── < constant            ───────────────────── < 2.5         bound(N)                                    N log(N)          

#handshakes(N) ────────────── ≈ 1/2      N² 

    N²/2 - N/2         (N²)/2   N/2         1/2 lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2 N→∞     N²       N→∞     N²     N²      N→∞  1                                ┕━━━┙              this is 0 in the limit of N→∞:              graph it, or plug in a really large number for N 

for(i=0; i<A; i++)        // A * ...     some O(1) operation     // 1  --> A*1 --> O(A) time  visualization:  |<------ A ------->| 1 2 3 4 5 x x ... x  other languages, multiplying orders of growth:   javascript, O(A) time and space     someListOfSizeA.map((x,i) => [x,i])                  python, O(rows*cols) time and space     [[r*c for c in range(cols)] for r in range(rows)] 

for every x in listOfSizeA:   // A * (...     some O(1) operation         // 1     some O(B) operation         // B     for every y in listOfSizeC: // C * (...         some O(1) operation       // 1))  --> O(A*(1 + B + C))     O(A*(B+C))        (1 is dwarfed)  visualization:  |<------ A ------->| 1 x x x x x x ... x  2 x x x x x x ... x ^ 3 x x x x x x ... x | 4 x x x x x x ... x | 5 x x x x x x ... x B  <-- A*B x x x x x x x ... x | ................... | x x x x x x x ... x v  x x x x x x x ... x ^ x x x x x x x ... x | x x x x x x x ... x | x x x x x x x ... x C  <-- A*C x x x x x x x ... x | ................... | x x x x x x x ... x v 

function nSquaredFunction(n) {     total = 0     for i in 1..n:        // N *         for j in 1..n:      // N *             total += i*k      // 1     return total } // O(n^2)  function nCubedFunction(a) {     for i in 1..n:                // A *         print(nSquaredFunction(a))  // A^2 } // O(a^3) 

for x in range(A):     for y in range(1..x):         simpleOperation(x*y)  x x x x x x x x x x | x x x x x x x x x   | x x x x x x x x     | x x x x x x x       | x x x x x x         | x x x x x           | x x x x             | x x x               | x x                 | x___________________| 

<----------------------------- N -----------------------------> x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 

<----------------------------- N -----------------------------> x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x 

   <----------------------------- N ----------------------------->  ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x  |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x  |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x  v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x 

[myDictionary.has(x) for x in listOfSizeA]  \----- O(1) ------/      --> A*1 --> O(A)