Notació O gran és una potent eina utilitzada en informàtica per descriure la complexitat temporal o espacial dels algorismes. Proporciona una manera estandarditzada de comparar l'eficiència de diferents algorismes en termes del seu pitjor rendiment. Comprensió Notació O gran és essencial per analitzar i dissenyar algorismes eficients.
En aquest tutorial, tractarem els conceptes bàsics Notació O gran , la seva importància i com analitzar la complexitat dels algorismes que utilitzen Gran O .
Taula de contingut
- Què és la notació Big-O?
- Definició de la notació Big-O:
- Per què és important la notació Big O?
- Propietats de la notació Big O
- Notacions de Big-O comunes
- Com determinar la notació Big O?
- Exemples matemàtics d'anàlisi en temps d'execució
- Exemples algorítmics d'anàlisi en temps d'execució
- Classes d'algoritmes amb nombre d'operacions i temps d'execució
- Comparació de la notació Big O, Big Ω (Omega) i Big θ (Theta)
- Preguntes freqüents sobre la notació Big O
Què és la notació Big-O?
Gran-O , comunament conegut com Ordre de , és una manera d'expressar el límit superior de la complexitat temporal d'un algorisme, ja que analitza el pitjor dels casos situació de l'algoritme. Proporciona un límit superior en el temps que triga un algorisme en termes de mida de l'entrada. Es denota com O(f(n)) , on f(n) és una funció que representa el nombre d'operacions (passos) que realitza un algorisme per resoldre un problema de mida n .
Notació Big-O s'utilitza per descriure el rendiment o la complexitat d'un algorisme. Concretament, descriu el en el pitjor dels casos en termes de temps o complexitat espacial.
Punt important:
- Notació O gran només descriu el comportament asimptòtic d'una funció, no el seu valor exacte.
- El Notació O gran es pot utilitzar per comparar l'eficiència de diferents algorismes o estructures de dades.
Definició de la notació Big-O:
Donades dues funcions f(n) i g(n) , ho diem f(n) és O(g(n)) si existeixen constants c> 0 i n 0 >= 0 tal que f(n) <= c*g(n) per a tot n>= n 0 .
En termes més senzills, f(n) és O(g(n)) si f(n) no creix més ràpid que c*g(n) per a tots els n>= n0on c i n0són constants.
Per què és important la notació Big O?
La notació Big O és una notació matemàtica que s'utilitza per descriure la complexitat temporal o l'eficiència en el pitjor dels casos d'un algorisme o la complexitat espacial en el pitjor dels casos d'una estructura de dades. Proporciona una manera de comparar el rendiment de diferents algorismes i estructures de dades, i de predir com es comportaran a mesura que augmenta la mida d'entrada.
La notació O gran és important per diverses raons:
- La notació Big O és important perquè ajuda a analitzar l'eficiència dels algorismes.
- Proporciona una manera de descriure com temps d'execució o requisits d'espai d'un algorisme creixen a mesura que augmenta la mida d'entrada.
- Permet als programadors comparar diferents algorismes i triar el més eficient per a un problema específic.
- Ajuda a entendre l'escalabilitat dels algorismes i a predir el seu rendiment a mesura que creixi la mida de l'entrada.
- Permet als desenvolupadors optimitzar el codi i millorar el rendiment general.
Propietats de la notació Big O:
A continuació es mostren algunes propietats importants de la notació Big O:
1. Reflexivitat:
Per a qualsevol funció f(n), f(n) = O(f(n)).
Exemple:
f(n) = n2, aleshores f(n) = O(n2).
2. Transitivitat:
Si f(n) = O(g(n)) i g(n) = O(h(n)), aleshores f(n) = O(h(n)).
Exemple:
f(n) = n3, g(n) = n2, h(n) = n4. Aleshores f(n) = O(g(n)) i g(n) = O(h(n)). Per tant, f(n) = O(h(n)).
Descàrrega turbo c++
3. Factor constant:
Per a qualsevol constant c> 0 i funcions f(n) i g(n), si f(n) = O(g(n)), aleshores cf(n) = O(g(n)).
Exemple:
f(n) = n, g(n) = n2. Aleshores f(n) = O(g(n)). Per tant, 2f(n) = O(g(n)).
4. Regla de suma:
Si f(n) = O(g(n)) i h(n) = O(g(n)), aleshores f(n) + h(n) = O(g(n)).
Exemple:
f(n) = n2, g(n) = n3, h(n) = n4. Aleshores f(n) = O(g(n)) i h(n) = O(g(n)). Per tant, f(n) + h(n) = O(g(n)).
5. Regla del producte:
Si f(n) = O(g(n)) i h(n) = O(k(n)), aleshores f(n) * h(n) = O(g(n) * k(n)) .
Exemple:
f(n) = n, g(n) = n2, h(n) = n3, k(n) = n4. Aleshores f(n) = O(g(n)) i h(n) = O(k(n)). Per tant, f(n) * h(n) = O(g(n) * k(n)) = O(n5).
6. Regla de composició:
Si f(n) = O(g(n)) i g(n) = O(h(n)), aleshores f(g(n)) = O(h(n)).
Exemple:
f(n) = n2, g(n) = n, h(n) = n3. Aleshores f(n) = O(g(n)) i g(n) = O(h(n)). Per tant, f(g(n)) = O(h(n)) = O(n3).
Notacions de Big-O comunes:
La notació Big-O és una manera de mesurar la complexitat temporal i espacial d'un algorisme. Descriu el límit superior de la complexitat en el pitjor dels casos. Vegem els diferents tipus de complexitats temporals:
1. Complexitat temporal lineal: complexitat de gran O(n).
La complexitat del temps lineal significa que el temps d'execució d'un algorisme creix linealment amb la mida de l'entrada.
Per exemple, considereu un algorisme que travessa una matriu per trobar un element específic :
Fragment de codi bool findElement(int arr[], int n, int key) { for (int i = 0; i < n; i++) { if (arr[i] == key) { return true; } } return false; }> 2. Complexitat de temps logarítmica: complexitat gran O(log n).
La complexitat del temps logarítmic significa que el temps d'execució d'un algorisme és proporcional al logaritme de la mida d'entrada.
Per exemple, a algorisme de cerca binària té una complexitat temporal logarítmica:
Fragment de codi int binarySearch(int arr[], int l, int r, int x) { if (r>= l) { int mid = l + (r - l) / 2; if (arr[mid] == x) retorna mid; if (arr[mit]> x) retorna binarySearch(arr, l, mid - 1, x); retornar cerca binària (arr, mig + 1, r, x); } retorn -1; }>>> 3. Complexitat del temps quadràtic: O gran (n2) Complexitat
La complexitat del temps quadràtic significa que el temps d'execució d'un algorisme és proporcional al quadrat de la mida d'entrada.
Per exemple, un senzill algorisme d'ordenació de bombolles té una complexitat temporal quadràtica:
Fragment de codiLa complexitat del temps cúbic significa que el temps d'execució d'un algorisme és proporcional al cub de la mida d'entrada. Per exemple, un ingenu algorisme de multiplicació de matrius té una complexitat temporal cúbica:
Fragment de codiLa complexitat del temps polinomial es refereix a la complexitat del temps d'un algorisme que es pot expressar com una funció polinomial de la mida d'entrada n . En gran O notació, es diu que un algorisme té complexitat temporal polinomial si la seva complexitat temporal és O (n k ) , on k és una constant i representa el grau del polinomi. Els algorismes amb complexitat de temps polinomial es consideren generalment eficients, ja que el temps d'execució creix a un ritme raonable a mesura que augmenta la mida de l'entrada. Alguns exemples comuns d'algorismes amb complexitat de temps polinomial inclouen complexitat temporal lineal O(n) , complexitat temporal quadràtica O(n 2 ) , i complexitat de temps cúbic O(n 3 ) .
6. Complexitat temporal exponencial: O gran (2n) Complexitat
La complexitat temporal exponencial significa que el temps d'execució d'un algorisme es duplica amb cada addició al conjunt de dades d'entrada.
Per exemple, el problema de generant tots els subconjunts d'un conjunt té una complexitat temporal exponencial:
Fragment de codi void generateSubsets(int arr[], int n) { for (int i = 0; i < (1 << n); i++) { for (int j = 0; j < n; j++) { if (i & (1 << j)) { cout << arr[j] << ' '; } } cout << endl; } }> Complexitat de temps factorial: complexitat de gran O(n!).
La complexitat del temps factorial significa que el temps d'execució d'un algorisme creix factorialment amb la mida de l'entrada. Això es veu sovint en algorismes que generen totes les permutacions d'un conjunt de dades.
Aquí teniu un exemple d'un algorisme de complexitat de temps factorial, que genera totes les permutacions d'una matriu:
Fragment de codi void permute(int* a, int l, int r) { if (l == r) { for (int i = 0; i <= r; i++) { cout << a[i] << ' '; } cout << endl; } else { for (int i = l; i <= r; i++) { swap(a[l], a[i]); permute(a, l + 1, r); swap(a[l], a[i]); // backtrack } } }> Si tracem els exemples de notació Big O més comuns, tindrem un gràfic com aquest:
jpa a la primavera
Com determinar la notació Big O?
Notació O gran és una notació matemàtica utilitzada per descriure el comportament asimptòtic d'una funció a mesura que la seva entrada creix infinitament gran. Proporciona una manera de caracteritzar l'eficiència dels algorismes i estructures de dades.
Passos per determinar la notació Big O:
1. Identifiqueu el terme dominant:
- Examineu la funció i identifiqueu el terme amb l'ordre de creixement més alt a mesura que augmenta la mida de l'entrada.
- Ignoreu els factors constants o els termes d'ordre inferior.
2. Determineu l'ordre de creixement:
- L'ordre de creixement del terme dominant determina la notació O Big.
3. Escriu la notació O gran:
- La notació O gran s'escriu com O(f(n)), on f(n) representa el terme dominant.
- Per exemple, si el terme dominant és n^2, la notació O gran seria O(n^2).
4. Simplifica la notació (Opcional):
- En alguns casos, el Marca Big O n es pot simplificar eliminant factors constants o utilitzant una notació més concisa.
- Per exemple, O(2n) es pot simplificar a O(n).
Exemple:
Funció: f(n) = 3n3+ 2n2+ 5n + 1
- Terme dominant: 3n3
- Ordre de creixement: cúbic (n3)
- Notació O gran: O(n3)
- Notació simplificada: O(n3)
Exemples matemàtics d'anàlisi en temps d'execució:
La taula següent il·lustra l'anàlisi del temps d'execució de diferents ordres d'algorismes a mesura que augmenta la mida d'entrada (n).
n registre (n) n n * registre (n) n^2 2^n n! 10 1 10 10 100 1024 3628800 20 2.996 20 59.9 400 1048576 2.432902e+1818
Exemples algorítmics d'anàlisi en temps d'execució:
La taula següent classifica els algorismes en funció de la seva complexitat en temps d'execució i proporciona exemples per a cada tipus.
Tipus Notació Algoritmes d'exemple Logarítmica O(log n) Cerca binària Lineal O(n) Cerca lineal Superlineal O(n log n) Ordenació en pila, ordenació combinada Polinomi O(n^c) Multiplicació matricial de Strassen, classificació de bombolles, ordenació de selecció, classificació d'inserció, classificació de cub Exponencial O(c^n) Torre de Hanoi Factorial O (n!) Expansió determinant per menors, algorisme de cerca de força bruta per al problema del venedor ambulant
Classes d'algoritmes amb nombre d'operacions i temps d'execució:
A continuació es mostren les classes d'algorismes i els seus temps d'execució en un ordinador que s'executa 1 milió d'operacions per segon (1 s = 10 6 μs = 10 3 msec) :
Classes de notació O Big
f(n)
Anàlisi Big O (nombre d'operacions) per a n = 10
Temps d'execució (1 instrucció/μs) constant
O(1)
1
1 μseg
logarítmica
O (inici de sessió)
3.32
3 μs
lineal
O(n)
10
10 μs
O(nlogn)
O(nlogn)
33.2
33 μs
quadràtica
O (n2)
102
100 μs
cúbic
O (n3)
103
1 ms
exponencial
O (2n)
1024
10 ms
factorial
O (n!)
funcions d'arduino
10!
3,6288 seg
Comparació de la notació Big O, Big Ω (Omega) i Big θ (Theta):
A continuació es mostra una taula que compara la notació Big O, la notació Ω (Omega) i la notació θ (Theta):
Notació Definició Explicació O gran (O) f(n) ≤ C * g(n) per a tots els n ≥ n0 Descriu el límit superior del temps d'execució de l'algoritme a pitjor dels casos . Ω (Omega) f(n) ≥ C * g(n) per a tots els n ≥ n0 Descriu el límit inferior del temps d'execució de l'algoritme al el millor dels casos . θ (Theta) C1* g(n) ≤ f(n) ≤ C2* g(n) per a n ≥ n0 Descriu els límits superior i inferior de l'algorisme temps d'execució .
En cada notació:
- f(n) representa la funció que s'està analitzant, normalment la complexitat temporal de l'algorisme.
- g(n) representa una funció específica que limita f(n) .
- C, C1, i C2 són constants.
- n 0 és la mida mínima d'entrada més enllà de la qual es manté la desigualtat.
Aquestes anotacions s'utilitzen per analitzar algorismes basats en els seus el pitjor dels casos (O gran) , el millor dels casos (Ω) , i cas mitjà (θ) escenaris.
Preguntes freqüents sobre la notació Big O:
Pregunta 1. Què és la notació Big O?
Resposta: La notació Big O és una notació matemàtica que s'utilitza per descriure el límit superior de la complexitat temporal d'un algorisme en termes de com creix en relació a la mida de l'entrada.
Pregunta 2. Per què és important la notació Big O?
Resposta: Ens ajuda a analitzar i comparar l'eficiència dels algorismes centrant-nos en el pitjor dels casos i entenent com s'escala el seu rendiment amb la mida de l'entrada.
Pregunta 3. Com es calcula la notació Big O?
Resposta: La notació Big O es determina identificant l'operació dominant en un algorisme i expressant la seva complexitat temporal en termes de n, on n representa la mida d'entrada.
Pregunta 4. Què significa O(1) en notació O gran?
Resposta: O(1) significa complexitat de temps constant, cosa que indica que el temps d'execució d'un algorisme no canvia independentment de la mida d'entrada.
Pregunta 5. Quina és la importància de diferents complexitats de Big O com O(log n) o O(n^2)?
Resposta: Diferents complexitats com O (log n) o O (n ^ 2) representen com s'escala el rendiment d'un algorisme a mesura que augmenta la mida d'entrada, proporcionant informació sobre la seva eficiència i escalabilitat.
Pregunta 6. La notació Big O també es pot aplicar a la complexitat espacial?
Resposta: Sí, la notació Big O també es pot utilitzar per analitzar i descriure la complexitat espacial d'un algorisme, indicant la quantitat de memòria que necessita en relació amb la mida d'entrada.
Article relacionat:
- Exemples d'anàlisi Big-O
- Disseny i anàlisi d'algorismes
- Tipus de notacions asimptòtiques en l'anàlisi de complexitat d'algorismes
- Anàlisi d'algorismes | Big – Ω (Big- Omega) Notació
- Anàlisi d'algorismes | petites o i petites notacions omega
