Je calcule toutes les variantes possibles du nombre d'entrée k pour 1, 2 ou 5 nombres. C'est un algorithme facile à comprendre:

//1,2,5
func foo(k: Int, result: [Int] = []) {
    if k == 0 {
        print(result)
        return
    }

    var one = result
    one.append(1)
    foo(k: k-1, result: one)

    if k >= 2 {
        var two = result
        two.append(2)
        foo(k: k-2, result: two)
    }

    if k >= 5 {
        var five = result
        five.append(5)
        foo(k: k-5, result: five)
    }
}

Donc, ça marche. Ma question est quelle est la complexité (grand O) de cet algorithme? Je suppose que c'est 3 ^ k, à cause de 3 appels récursifs à l'intérieur. Veuillez prouver ou expliquer votre opinion.

1
Ivan Vavilov 2 avril 2017 à 21:50

2 réponses

Meilleure réponse

Votre analyse de O (3 ^ n) est correcte, mais ce n'est pas une limite serrée car bien que le facteur de branchement soit (principalement) 3, la hauteur des branches droites (n-5) est plus petite que le milieu (n-2) et branche gauche (n-1).

La relation de récurrence décrivant votre code est: T(n) = T(n-1) + T(n-2) + T(n-5) + 1

En soustrayant T(n+1) de T(n) (une astuce standard pour se débarrasser de la constante), nous obtenons:

T(n+1) - T(n) = T(n) + T(n-1) + T(n-4) + 1 - T(n-1) - T(n-2) - T(n-5) - 1
T(n+1) = 2T(n) - T(n-2) + T(n-4) - T(n-5)

Ceci est une relation de récurrence linéaire homogone, ainsi a des solutions de la forme:

sum(A_i * a_i^n for i=0..5)

Où A_i sont des constantes (complexes) et a_i sont les racines de l'équation x ^ 6 = 2x ^ 5 - x ^ 3 + x - 1.

Ainsi, l'ordre de croissance de T (n) sera O (a ^ n) où a est la racine de grandeur la plus grande de l'équation. Cela se trouve être réel, et est d'environ 1,7049.

Ainsi, votre code s'exécute dans le temps O (1,705 ^ n). Ce qui est bien meilleur que O (3 ^ n), bien que toujours exponentiel.

2
Paul Hankin 2 avril 2017 à 21:32

Vous avez raison, et il y a deux clés pour l'analyse. Puisque vous définissez la fonction avec k comme argument, écrivons la complexité en termes de k:

Pour k >= 5, foo résoudre le problème de taille k est réduit à s'appeler 3 fois pour résoudre des problèmes plus petits, chacun de taille k - c, où c est une constante (dans votre cas au plus 5). Ainsi, vous pouvez écrire la complexité temporelle de foo comme suit:

3 * f(k-1) >= f(k) >= 3 * f(k-5)

Et la solution est clairement f(k) = O(3^k), que vous pouvez prouver par exemple en mesurant le nombre de feuilles dans l'arbre de récursivité.

1
pkacprzak 2 avril 2017 à 19:28