(ya que esta es una respuesta más larga, lee la negrita para obtener un resumen )
Tomemos tu ejemplo y veamos paso a paso, entendiendo el propósito detrás de lo que estamos haciendo. Comenzamos con su función y el objetivo de encontrar su notación Big Oh:
f(n) = 6n+4
Primero, sea O(g(n))
la notación Big Oh que estamos tratando de encontrar para f(n)
. De la definición de Big Oh, necesitamos encontrar un simplificado g(n)
donde existan algunas constantes c
y n0
donde c*g(n) >= f(n)
es verdadero para todos n
' s mayor que n0
.
Primero, vamos a elegir g(n) = 6n + 4
(que daría O(6n+4)
en Big Oh). En este caso, vemos que c = 1
y cualquier valor de n0
cumplirán los requisitos matemáticos de nuestra definición de Big Oh, ya que g(n)
siempre es igual a f(n)
:
c*g(n) >= f(n)
1*(6n + 4) >= 6n + 4 //True for all n's, so we don't need to pick an n0
En este punto hemos cumplido con los requisitos matemáticos. Si nos detuviéramos en O(6n+4)
, está claro que esto no es más útil que escribir f(n)
, por lo que perdería el verdadero propósito de la notación Big Oh: comprender el tiempo general- ¡La complejidad de un algoritmo! Por lo tanto, avancemos al siguiente paso: la simplificación.
Primero, ¿podemos simplificar el 6n
para que Big Oh sea O(4)
? ¡No! (Ejercicio para el lector si no entienden por qué)
Segundo, ¿podemos simplificar el 4
para que el Big Oh sea O(6n)
? ¡Sí! En ese caso, g(n) = 6n
, entonces:
c*g(n) >= f(n)
c*6n >= 6n + 4
En este punto, vamos a elegir c = 2
ya que entonces el lado izquierdo aumentará más rápido (en 12) que el lado derecho (en 6) para cada incremento de n
.
2*6n >= 6n + 4
Ahora debemos encontrar un n0
positivo donde la ecuación anterior sea verdadera para todos los n
's mayores que ese valor. Como ya sabemos que el lado izquierdo está aumentando más rápido que el derecho, todo lo que tenemos que hacer es encontrar una solución positiva. Por lo tanto, dado que n0 = 2
hace que lo anterior sea cierto, sabemos que g(n)=6n
, o O(6n)
es una posible notación de Big Oh para f(n)
.
Ahora, ¿podemos simplificar el 6
para que el Big Oh sea O(n)
? ¡Sí! En ese caso, g(n) = n
, entonces:
c*g(n) >= f(n)
c*n >= 6n + 4
Seleccionemos c = 7
ya que la izquierda aumentaría más rápido que la derecha.
7*n >= 6n + 4
Vemos que lo anterior será cierto para todos los n
's mayor o igual que n0 = 4
. Por lo tanto, O(n)
es una posible notación de Big Oh para f(n)
. ¿Podemos simplificar más g(n)
? ¡No!
Finalmente, hemos encontrado que la notación Big Oh más simple para f(n)
es O(n)
. ¿Por qué pasamos por todo esto? Porque ahora sabemos que f(n)
es lineal , ya que su notación Big Oh es de complejidad lineal O(n)
. Lo bueno es que ¡ahora podemos comparar la complejidad de tiempo de f(n)
con otros algoritmos! Por ejemplo, ahora sabemos que f(n)
tiene una complejidad de tiempo comparable a las funciones h(n) = 123n + 72
, i(n) = n
, j(n) = .0002n + 1234
, etc; porque utilizando el mismo proceso de simplificación descrito anteriormente, todos tienen una complejidad de tiempo lineal de O(n)
.
Dulce!!!