Complexitat temporal

Archiu:Comparison computational complexity.svg

Gràfics de funcions comunament utilisades en l'anàlisis d'algoritmes, que mostren el número d'operacions N versus el tamany d'entrada n per a cada funció

En informàtica, la complexitat temporal és la complexitat computacional que descriu la cantitat de temps que du eixecutar un algoritme. La complexitat temporal s'estima comunament contant el número d'operacions elementals realisades per l'algoritme, suponent que cada operació elemental requerix una cantitat fixa de temps. Per lo tant, la cantitat de temps necessari i el número d'operacions elementals realisades per l'algoritme diferixen en un factor constant com a màxim.

Ya que el temps d'eixecució d'un algoritme pot variar entre diferents entrades del mateix tamany, comunament es considera la complexitat temporal del pijor cas, que és la cantitat màxima de temps requerida per a les entrades d'un tamany determinat. Menys comú, i usualment especificat explícitament, és la complexitat del case promig, que és el promig del temps necessari per a les entrades d'un tamany donat (açò té sentit perque solament hi ha un número finito d'entrades possibles d'un tamany donat). En abdós casos, la complexitat temporal generalment s'expressa com una funció del tamany de l'entrada.^[1] Ya que esta funció és generalment difícil de calcular exactament, i el temps d'eixecució per a entrades chicotetes generalment no és conseqüent, un comunament s'enfoca en el comportament de la complexitat quan aumenta el tamany d'entrada, és dir, el comportament asintòtic de la complexitat. Per lo tant, la complexitat temporal s'expressa comunament usant la notació O gran, típicament $O (n)$ , $O (n \log n)$ , $O (n^{α})$ , $O (2^{n})$ , etc., a on $n$ és el tamany d'entrada en unitats de bits necessaris per a representar l'entrada.

Les complexitat algorítmiques es classifiquen segons el tipo de funció que apareix en la notació O gran. Per eixemple, un algoritme en complexitat temporal $O (n)$ és un algoritme de temps llineal i un algoritme en complexitat de temps $O (n^{α})$ per alguna constant $α > 1$ és un algoritme de temps polinòmic .

Taula de complexitat temporals comunes

La següent taula resumix algunes classes de complexitat de temps comunament trobades. En la taula, poly(x) = x^O(1), és dir, polinomial en x .

Nom	Classe de complexitat	Temps d'eixecució (T(n))	Eixemples de temps d'eixecució	Algoritmes d'eixemple
Temps constant		O(1)	10	Trobar la mijana en un array ordenat de números.
Temps invers de la funció de Ackermann		O(α(n))		Temps amortisat per operació usant un conjunt disjunto
Temps de [[logaritmo iterado]]		O(logn)		Coloració distribuïda de grafos
Log-logaritmico		O(log log n)		Temps amortisat per operació usant una coa de prioritats^[2] acotada.
Temps logarítimico	DLOGTIME	O(log n)	log n, log(n²)	Busca binaria
Temps polilogarítmico		poly(log n)	(log n)²
Poder fraccional		$O (n c)$ a on $0 < c < 1$	n^1/2, n^2/3	Buscant en un arbre kd
Temps llineal		O(n)	n, 2n + 5	Trobar el item més gran o més chicotet en un array desordenat. Kadane's algorithm
Temps "n log-estrela n"		O(n log* n)		Algoritme de triangulació de polígons de Seidel
Temps linealitmico		O(n log n)	n log n, log n!	L'ordenament per comparació més ràpit possible; Transformada ràpida de Fourier
Temps cuasilineal		n poly(log n)
Temps quadràtic		O(n²)	n²	Bubble sort; Insertion sort; Convolución directa
Temps cúbic		O(n³)	n³	Multiplicació ingènua de dos matrius de n×n. Càlcul decorrelació parcial.
Temps polinòmic	P	2^O(log n) = poly(n)	n² + n, n¹⁰	Algoritme de Karmarkar para programació llineal; Test de primalidad AKS^[3]^[4]
Temps cuasipolinomial	QP	2^poly(log n)	n^log log n, n^log n	O(log² n), milloralgoritme conegut d'aproximació per al el problema de l'arbre de Steiner directe
Temps sub-exponencial (primera definició)	SUBEXP	O(2^{n^ε}) para tot ε > 0	O(2^{log n^{log log n}})
Temps sub-exponencial (segona definició)		2^o(n)	2^{n^1/3}	Millor algoritme conegut para for factorización de sancers; anteriorment el millor algoritme per a el problema de l'isomorfisme de grafos
Temps exponencial (en exponent llineal)	I	2^O(n)	1.1ⁿ, 10ⁿ	Resolució del problema del viajante usant programació dinàmica
Temps exponencial	EXPTIME	2^poly(n)	2ⁿ, 2^n²	Resolució de multiplicació de matrius encadenades via brute-force search
Temps factorial		O(n!)	n!	Resolent el problema del viager usant busca de força bruta
Temps exponencial doble	2-EXPTIME	2^{2^poly(n)}	2^2ⁿ	Deciding the truth of a given statement in Aritmètica de Presburguer

Temps constant

Es diu que un algoritme és temps constant (també escrit com a temps O(1)) si el valor de T(n) està llimitat per un valor que no depén del tamany de l'entrada. Per eixemple, accedir a qualsevol element individual en una matriu requerix temps constant, ya que solament es deu realisar una operació per a localisar-ho. De manera similar, trobar el valor mínim en una matriu ordenada en orde ascendent també és una operació de temps constant ya que el resultat és sempre el primer element. No obstant, trobar el valor mínim en una matriu desordenada no és una operació de temps constant ya que és necessari escanejar cada element de la matriu per a determinar el valor mínim. Per lo tant, este cas és una operació de temps llineal, que pren temps O(n). No obstant, si el número d'elements es coneix de bestreta i no canvia encara es pot dir que dit algoritme s'eixecuta en temps constant.

A pesar del nom "temps constant", el temps d'eixecució no té que ser independent del tamany del problema, pero un llímit superior per al temps d'eixecució té que estar llimitat independentment del tamany del problema. Per eixemple, la tasca "intercanvia els valors de a i b si és necessari per a que a ≤ b " es diu de temps constant encara que el temps puga dependre de si ya és cert o no que a ≤ b . No obstant, hi ha una constant t tal que el temps requerit és sempre com a màxim t .

Estos són alguns eixemples de fragments de còdic que s'eixecuten en temps constant. :

int index = 5;
int item = llesta[index];
if (condició verdadera) then
  realisar alguna operació que s'eixecuta en temps constant
else
  realisar alguna atra operació que s'eixecute en temps constant
for i=1 to 100
  for j=1 to 200
   realisar alguna operació que s'eixecuta en temps constant

Si T(n) és O(qualsevol valor constant) s'indica en notació estàndar com a T(n) sent O(1).

Referències

↑ Sipser, Michael (2006). Introduction to the Theory of Computation, Course Technology Inc. ISBN 0-619-21764-2.
↑ (1990).Information Processing Letters.35(4)
183–189.doi:10.1016/0020-0190(90)90022-P.
↑ Tao, Terence (2010). «1.11 The AKS primality test», An epsilon of room, II: Pages from year three of a mathematical blog, Providence, RI: American Mathematical Society, pp. 82–86. doi:10.1090/gsm/117. ISBN 978-0-8218-5280-4.
↑

Referències

Este artícul conté una traducció derivada de «Complejidad temporal» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[Sipser-1] Sipser, Michael (2006). Introduction to the Theory of Computation, Course Technology Inc. ISBN 0-619-21764-2.

[2] (1990).Information Processing Letters.35(4)
183–189.doi:10.1016/0020-0190(90)90022-P.

[tao-aks-3] Tao, Terence (2010). «1.11 The AKS primality test», An epsilon of room, II: Pages from year three of a mathematical blog, Providence, RI: American Mathematical Society, pp. 82–86. doi:10.1090/gsm/117. ISBN 978-0-8218-5280-4.

[4] ↑

[1]

[2]

[3]

[4]