Notación Big-O (que es un término general que abarca [matemáticas] O (f (n), \ Theta (f (n)), \ omicron (f (n)), \ Omega (f (n)) [/ math ], etc.) se refiere al crecimiento de la función cuando [math] n [/ math] es grande. Decir que [math] f (n) = \ Theta (g (n)) [/ math] significa que hay son dos constantes (positivas) [matemáticas] a, b [/ matemáticas] tales que para algunas [matemáticas] N [/ matemáticas], si [matemáticas] n> N, ag (n) \ leq f (n) \ leq bg (n) [/ matemáticas].
Como ejemplo, considere [math] f (n) = 45n + 100 \ sin n [/ math]. Esta función fluctúa enormemente, pero puedo afirmar con certeza que cuando [matemáticas] n> 200, 44n <45n -100 <45n – 100 \ sen n <45n + 100 <46n [/ matemáticas], por lo tanto, puedo afirmar que [ matemáticas] 45n + 100 \ sin n = \ Theta (n) [/ matemáticas]. Las dos constantes son [matemáticas] a = 44, a = 46 [/ matemáticas].
Para tomar un ejemplo más realista, considere el tipo de selección:
- ¿Quiénes son las estrellas en ascenso en la informática teórica?
- Estoy tomando SL Maths para el Diploma IB, ¿sería esto suficiente para universidades como UCB, UCLA, GaTech for Computer Science?
- Cómo construir una computadora fuera del agua, y cómo ayuda esto con Navier-Stokes
- ¿Realmente necesito una sólida formación en matemáticas para comenzar a aprender programación?
- ¿Cómo se puede lograr acceso aleatorio en O (log n)?
[código]
int [] SelectionSort (int [] array) {
var n = array.Length;
para (var i = 0; i <n; i ++) {
var más grande = i;
para (var j = i; j <n; j ++) {
if (matriz [j]> matriz [más grande])
mayor = j;
}
var temp = matriz [i]; matriz [i] = matriz [más grande]; matriz [más grande] = temp;
}
matriz de retorno;
}
[/código]
Este código hace [math] \ frac {n (n-1)} {2} [/ math] comparaciones, y [math] n [/ math] intercambios. Si cada intercambio lleva tiempo [math] s [/ math] y cada tiempo de comparación [math] c [/ math], y hay tiempo [math] d [/ math] sobrecarga que se realiza una vez cada vez que se llama a esta función, independientemente de qué tan grande es la matriz, entonces el tiempo total utilizado es [matemática] T (n) = \ frac {n (n-1)} {2} c + sn + d = \ frac {c} {2} n ^ 2 + \ frac {2s-c} {2} n + d = \ Theta (n ^ 2) [/ math]. Puedo decir que, para grandes [matemáticas] n [/ matemáticas], el primer término será el término dominante. En cualquier momento cuando [matemáticas] n> \ frac {2s} {c} [/ matemáticas] el primer término será mayor que el segundo, y cuando [matemáticas] n> \ frac {d} {| 2s-c | } [/ math] el segundo término va a ser más grande que el tercero. Entonces, para grandes [matemáticas] n [/ matemáticas], puedo decir que [matemáticas] \ frac {c} {4} n ^ 2 <T (n) <cn ^ 2 [/ matemáticas], entonces [matemáticas] T ( n) = \ Theta (n ^ 2) [/ matemáticas].
En realidad, en este análisis no me importa cuál debe ser el valor exacto de [matemáticas] N [/ matemáticas], ni cuáles son los valores exactos de [matemáticas] a, b [/ matemáticas]. Puedo calcularlo, pero como puede ver, depende de la naturaleza exacta de la implementación.
