Sí, tu suposición es correcta. Es O (n) solamente. Y es la explicación gradual del método de sustitución.
Somos una relación de recurrencia como: –
T (n) = T (n / 2) + n
- Una fábrica produce bombillas defectuosas con cierta probabilidad, p. Se sabe que p es pequeño: alrededor del 1%, pero se desconoce el valor exacto. ¿Cuál es el tamaño de muestra que tomaría para estimar el valor de p?
- ¿Por qué una calculadora simple solo toma hasta 9 dígitos como entrada?
- ¿Existen los números irracionales que no son construibles en la recta numérica real?
- ¿Qué temas en matemáticas debo aprender para la programación competitiva?
- ¿Cuánto conocimiento matemático profundo deberías tener como diseñador de juegos?
Ahora resolviendo esto a través del método de sustitución
T (n) = T (n / 2) + n
T (n) = T (n / 2 ^ 2) + n / 2 + n
T (n) = T (n / 2 ^ 3) + n / 2 ^ 2 + n / 2 + n
.
.
. k veces repitiendo, obtenemos
T (n) = Tn / 2 ^ k + n / 2 ^ k-1 n / 2 ^ k-2 + …… .. + n / 2 + n
log (n) veces repitiendo …
T (n) = T (n / 2 ^ logn) + n / 2 ^ logn-1 + n / 2 ^ logn-2 + ……… + n / 2 + n
Dado que T (n / 2 ^ logn) = T (n / n) {propiedad de log}
T (n / n) = 1; por lo tanto nuestra función se convierte en:
T (n) = 1+ n / 2 ^ logn-1 + n / 2 ^ logn-2 + ………… .. + n / 2 + n
Podemos escribir en orden inverso como: –
T (n) = n + n / 2 + n / 2 ^ 2 + ……………… + n / 2 ^ logn-1 +1
Tomando n común de todos los términos, obtenemos: –
T (n) = n (1 + 1/2 + 1/2 ^ 2 + ……………………… + n / 2 ^ logn-1) + 1
Aquí obtenemos un GP decreciente con una relación 1/2 y el número total de términos son logn, por lo tanto, usando la fórmula de la suma de n términos de GP, obtendremos: –
T (n) = n ((1 – 1/2 ^ logn) / 1–1 / 2) + 1
T (n) + n ((1 – 1 / n) / 1/2) {ya que 2 ^ logn es igual a n}
Como 1 / n se acerca a 0, por lo tanto, lo ignoramos y obtenemos
T (n) = n / (1/2) +1
T (n) = 2n +1
T (n) = O (n) {en las notaciones asintóticas ignoramos las constantes}
Nota: Hay algunos otros métodos para resolver, como el teorema de Master. Pero funciona solo en algunos casos especiales y en otros casos da respuestas incorrectas. Por lo tanto, lo recomendaré solo con el Método de sustitución.
