Como calcular a complexidade do tempo [duplicado]

Question

qualquer um pode ajudar a explicar porque esta função

F (n) = F (n / 3) + 1 com F (0) = 0

Pode ter complexidade de tempo de O (Log n) com log de base 3.

Existe uma notação matemática ou qualquer coisa que possa ajudar a me explicar como obter o resultado. obrigado

Answer 1

Por substituição, pode ser feito simplesmente:

F(n) = F(n/3) + 1 = F(n/3^2) + 1 + 1 = 1 + 1 + ... + 1 (log_3(n) times)

À medida que cada vez né dividido por 3e 1é adicionado ao resultado, se supusermos n = 3^k, F(n) = k. Portanto F(n) = O(log(n)),. A constante (> 1) na base do logaritmo não tem impacto na ordem de complexidade, ou seja, log_a(n) = Theta(log_b(n))( a,b > 1).