Si T (1) = 2 y T (n) viene dado por T (n / 2) + c para n> 1, ¿cómo calcula la complejidad del algoritmo?

Para ser claros, supongo que T (n) describe la complejidad del algoritmo que desea calcular, por lo que, en cierto sentido, ya conoce la complejidad del algoritmo. Es T (n). Por supuesto, esto probablemente no sea lo que está preguntando. Lo que probablemente quiera saber es cómo encontrar una expresión de forma cerrada para T (n) en términos de la notación big-O.

La teoría general está dada por el teorema del Maestro, que se puede encontrar aquí:

Teorema maestro – Wikipedia

De hecho, utilizando el teorema del Maestro, puede llegar inmediatamente a la respuesta.

Si solo desea la respuesta, hay “calculadoras de teoremas maestros” en línea (Ejemplo: Solucionador de teoremas maestros (JavaScript)). Sin embargo, si se trata de una tarea, recomiendo tratar de entender cómo funcionan antes de usar las calculadoras. El instructor probablemente querrá saber cómo llegó a la respuesta en cualquier caso.

Sin embargo, para desarrollar una intuición para la respuesta, comience conectando algunos números.

T (1) = 2

Ahora, descubra T (2) y T (3), etc. Sin embargo, debido a que siempre estamos dividiendo por 2 en el cálculo de T (n) = T (n / 2) + c, solo voy a mirar potencias de 2 para n. Tenga en cuenta que si tuviera algo como T (n) = T (n / 5) + [algo], en su lugar miraría las potencias de 5. Si tuviera T (n) = T (n – 3) + [algo] , Miraría cada tercer valor (p. Ej., T (1), T (4), T (7), …).

T (2) = T (2/2) + c = T (1) + c = 2 + c

T (4) = T (4/2) + c = T (2) + c = 2 + c + c = 2 + 2c

T (8) = T (8/2) + c = T (4) + c = 2 + 2c + c = 2 + 3c

T (16) = T (16/2) + c = T (8) + c = 2 + 3c + c = 2 + 4c

Espero que comience a ver un patrón aquí: cuando n es una potencia de 2, incrementamos el valor en una sola cantidad constante: c.

Como estamos hablando de big-O, podemos ignorar el valor 2, y podríamos dejar que c = 1, por lo que esto nos daría el mismo valor de big-O que:

T (2) = 1

T (4) = 2

T (8) = 3

T (16) = 4

T (32) = 5

etc.

¿Puedes pensar en una función que se comporte de esta manera?

Te dejo la conclusión final. Espero que esto haya proporcionado algunas ideas.

Si c es una constante, entonces podemos usar el método maestro para resolver esta recurrencia.

[matemáticas] T (n) = T (\ frac {n} {2}) + c [/ matemáticas]

En el método maestro, observamos [math] \ log_b a [/ math] que es [math] \ log_2 1 = 0. [/ math]

Ahora comparamos [matemáticas] n ^ 0 = 1 [/ matemáticas] con c.

Como 1 y c son polinómicamente iguales, este es el caso 2 del método maestro y obtenemos

[matemáticas] T (n) = \ Theta (\ log n). [/matemáticas]