Quel serait le Big O de cette fonction:

def foo(n):
    if (n <= 1):
        return 0
    else:
        return n + foo(n/2) + foo(n/2)

Je pense que cela pourrait O (2 ^ logn) parce que dans chaque appel, il y a deux autres appels et n est divisé par 2 jusqu'à ce qu'il arrive à 1, donc le logn.

0
David Meléndez 28 août 2020 à 19:31

2 réponses

Meilleure réponse

Oui, c'est O (2 logn ) , qui équivaut vraiment à O (n) .

Vous pouvez l'analyser comme suit:

T (n) = 1 + 2T (n / 2)
= 1 + 2 (1 + 2T (n / 4)) = (2²-1) + 2²T (n / 4)
= (2²-1) + 2² (1 + 2T (n / 8)) = (2³-1) + 2³T (n / 8)
...
= (2 connexion - 1) + 2 connexion
= (n-1) + 2n
= O (n)

Cela peut être un résultat surprenant, mais un extrait de code mesurant la fraction entre n et le nombre d'appels de foo, illustre cette complexité temporelle:

let counter;

function foo(n) {
    counter++;
    if (n <= 1)
        return 0;
    else
        return n + foo(n/2) + foo(n/2);
}

for (let n = 1; n < 100000; n*=2) {
    counter = 0;
    foo(n);
    console.log(counter/n);
}
3
trincot 28 août 2020 à 18:04

De plus, vous pouvez également utiliser le théorème maître (le premier cas). Dans votre cas comme la relation récursive est T(n) = 2T(n/2) + 1, si nous voulons écrire la relation sous la forme T(n) = aT(n/b) + f(n), nous aurons:

a = 2, b = 2, f(n) = 1
=> c_crit = log2(2) = 1

Comme f(n) = 1 = O(n^c) pour tous c > 0, nous pouvons trouver un 0 < c < 1 qui c < c_crit = 1. Par conséquent, le premier cas du théorème maître est satisfait. Par conséquent, T(n) = \Theta(n).

1
OmG 28 août 2020 à 22:48