|
Página 7 de 8
Hay muchas operaciones referidas a estos órdenes de complejidad que se pueden aplicar, pero en general, vamos a comentar algunas de las más sencillas. Todas ellas tienen que ver con el cálculo de límites. Estas reglas nos permiten "simplificar".... y dado un orden de complejidad, poder llegar a uno de los de la tabla anterior.
| REGLA |
EJEMPLOS |
Si k es una constante y f(n)∈O(g(n)) ⇒ kf(n)∈O(g(n))
Es decir, si una funcion f(n) es de un orden g, esa función multiplicada por una constante también es del mismo orden. |
- 3n2 ∈ O(n2)
- 14 ∈ O(1) porque 14=14×1
- 43×2n ∈ O(2n)
- 7n ∈ O(n)
|
|
Si f(n)∈O(h(n)) y g(n)∈O(h(n))⇒f(n)+g(n)∈O(h(n))
Es decir, si dos funciones están en el mismo orden, la suma de ambas también lo está.
|
- 3n2+2n2∈O(n2)
- 2n+5n∈O(cn)
|
Si f(n) es un polinomio de grado m ⇒ f(n)∈O(nm)
Esto también vale para m=1. |
- 6n3+n2+3n+1 ∈ O(n3)
- n7+3n2+1 ∈ O(n7)
- 7n+12 ∈ O(n)
|
Si F(n)=f(n)+g(n) y f(n)∈O(h(n)), g(n)∈O(j(n)) ⇒ f(n)+g(n) ∈ O(h(n)+j(n))
Cuando una funcion de complejidad F(n) se puede descomponer en la suma de dos funciones (f y g) las cuales pertenecen a órdenes de complejidad distintos, el orden de F(n) es el orden de la suma de los órdenes de f y g. |
|
Si F(n)=f(n)×g(n) y f(n)∈O(h(n)), g(n)∈O(j(n)) ⇒ f(n)+g(n) ∈ O(h(n)×j(n))
Cuando una funcion de complejidad F(n) se puede descomponer en el producto de dos funciones (f y g) las cuales pertenecen a órdenes de complejidad distintos, el orden de F(n) es el orden del producto de los órdenes de f y g. |
|
|
O(f(n)+g(n))⊂O(max{f(n),g(n)})
Cuando en un orden tenemos una suma, predomina el orden mayor.
|
|
Es decir, si por ejemplo obtengo que la complejidad de un algoritmo es 6n3+5n+1, es correcto decir que la complejidad de ese algoritmo es del orden de O(6n3+5n+1), ya que todas la funciones de ese orden, incluida 6n3+5n+1 están asintóticamente acotadas por ella. Pero con esas reglas, también podemos decir que la complejidad es del orden de O(6n3+5n), y también del O(6n3) y también del órden O(n3), porque
O(6n3+5n+1) ⊂ O(6n3+5n) ⊂ O(6n3) ⊂ O(n3)
Pero normalmente, nos basta con saber que un algoritmo tiene un orden O(n3), que es uno de los órdenes de uso común en lugar de afinar más y decir que el orden es O(6n3+5n+1) porque realmente cuando n es grande no nos aporta nada afinar más.
|
Artículos 
