Comment calculer la complexité temporelle [dupliquer]

Question

n'importe qui peut aider à expliquer pourquoi cette fonction

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

Peut avoir une complexité temporelle de O (Log n) avec log base 3.

Y a-t-il une notation mathématique ou quoi que ce soit qui puisse m'aider à m'expliquer comment obtenir le résultat. Merci

Answer 1

Par substitution, cela peut être fait simplement:

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

Comme chaque fois nest divisé par 3et 1est ajouté au résultat, si nous supposons n = 3^k, F(n) = k. Par conséquent, F(n) = O(log(n)). La constante (> 1) dans la base du logarithme n'a aucun impact sur l'ordre de complexité, c'est-à-dire log_a(n) = Theta(log_b(n))( a,b > 1).