La complexité de l'algorithme avec entrée est de taille fixe

Question

J'ai trouvé quelques références à propos de la notation O grand, mais autant que je peux comprendre la complexité de l'algorithme est une fonction de la taille des données d'entrée. Par exemple, si la complexité du tri à bulles est O(n^2), n est la taille du tableau d'entrée. Droite? Mais, comment puis-je déterminer la complexité de l'algorithme qui a une taille d'entrée fixe et dépend des valeurs d'entrée. Par exemple, trouver le plus grand commun diviseur (GCD) ressemblerait à ceci:

def GCD(x, y): 
    while x != y: 
     if x < y: 
      x, y = y - x, x 
     else: 
      x, y = x - y, x 
    return x 

Quelle est la complexité de cet algorithme? Et comment est-ce déterminé?

Éditer: Nom modifié de la fonction et nom corrigé de l'algorithme. ShreevatsaR, merci de l'avoir signalé.

Answer 1

Les gens jouent un peu vite et perdent avec la notation big-O. Dans le cas de GCD, ils le font généralement de 2 façons:

1) Vous avez raison, la complexité algorithmique, et donc la notation O-Big, doit être exprimée en termes de taille dans les bits de l'entrée , pas en termes de valeurs de l'entrée. C'est ainsi que P, NP et ainsi de suite sont définis. En supposant que l'entrée binaire et arbitrairement-grands nombres (comme une représentation BigNum), et N le nombre de bits d'entrée, votre GCD nécessite au plus 2^N soustractions, dont chacune nécessite un temps O (N) pour parcourir chaque chiffre de la les nombres étant soustraits. Donc c'est O (N * 2^N). GCD peut bien sûr être fait beaucoup plus rapidement si vous utilisez la division plutôt que la soustraction: O (N^2). Donc, quand nous disons que testing primality was proved in 2002 to be done in polynomial time, c'est la définition technique de la complexité, et nous voulons dire polynomial dans le nombre de chiffres (qui est la partie difficile), pas polynomial dans le nombre d'entrée lui-même (qui est trivialement facile à faire en "temps sous-linéaire" en utilisant la division d'essai). En pratique, pour les algorithmes qui prennent un nombre fixe d'entrées entières, il est plus pratique de parler de complexité comme si N était l'entrée elle-même, pas la taille de l'entrée. Ce n'est pas dangereux tant que vous comprenez ce que vous voulez dire dans les cas qui peuvent être ambigus.

2) En pratique, les entrées entières sont souvent de taille fixe, 32 bits ou autre, et leurs opérations telles que l'addition, la multiplication et la division sont O (1). Nous utilisons ces faits de manière sélective dans notre analyse d'ordre. Techniquement si votre programme GCD n'accepte que les entrées jusqu'à (2^32-1), alors c'est O (1). Il a une limite supérieure fixe sur son temps de fonctionnement. Fin de l'analyse

Bien que techniquement correct ce n'est pas une analyse très utile. Presque tout ce que vous faites sur un vrai ordinateur est O (1) sur la même base, que la taille du problème est limitée par le matériel.

Il est généralement plus pratique d'accepter que l'addition est O (1) parce que les nombres sont de taille fixe, mais ignorer que GCD est aussi O (1), prétendre que son comportement est dans la plage [1, 2^32) s'étend à l'infini et l'analyse sur cette base. Alors avec N le maximum des deux entrées, il en résulte des soustractions O (N): O (N), chacune prenant un temps constant. Encore une fois, cela n'est pas ambigu une fois que vous connaissez les termes de référence, mais méfiez-vous de comparer incorrectement la première analyse de l'algorithme d'Euclide avec division, O (N^2), avec cette analyse de l'algorithme avec soustraction, O (N). N n'est pas le même dans chaque, et la soustraction est pas plus rapide ;-)

Answer 2

la taille d'entrée est la somme des tailles des numéros x et y (par exemple le nombre de chiffres du nombre)

Answer 3

complexité Big O est le pire des cas le comportement d'exécution asymptotique. Ce n'est pas nécessairement dépendant de la taille d'entrée (quantité d'entrées) d'un algorithme particulier - bien que ce soit souvent le cas. En d'autres termes, c'est la fonction limitative qui décrit l'exécution car les entrées sont prises à l'infini.

Dans votre cas, si x ou y sont illimités, l'exécution asymptotique l'est également. Si non, pensez à l'heure d'exécution si x = 1, et y = Int32.Max?

Answer 4

La notation Big-O doit spécifier ce qui est mesuré. Par exemple, la notation Big-O pour les algorithmes de tri mesure généralement le nombre de comparaisons.

Votre exemple GCD peut être mesuré en comparant les valeurs de x et y par rapport au nombre d'instructions exécutées. Regardons de plus près:

def GCD(x, y): 
    while x != y:    # 1 
     if x < y:    # 2 
      x, y = y - x, x  # 3 
     else:     # 4 
      x, y = x - y, x  # 5 
    return x     # 6 

Travailler de l'intérieur vers l'extérieur. Quelles que soient les valeurs x et y, les étapes 3 et 5 prennent toujours une instruction. Par conséquent, l'instruction if de l'étape 2 prendra toujours deux instructions. La question la plus difficile est l'étape 1. À chaque itération, x ou y sera réduit de la plus petite valeur. Supposons que x > y. L'une des deux choses:

• Si elle a commencé cette x % y == 0, la boucle sera exécutée (x/y) - 1 fois et le programme arrêtera.

• Sinon, x sera réduite (x/y) fois avant qu'il ne soit plus petit que y et le programme se poursuivra.

Vous pouvez facilement mesurer le nombre d'instructions pour une donnée x et y.Vous pouvez facilement montrer que, pour un nombre donné z, vous n'aurez jamais besoin de plus de z - 1 soustractions - ou instructions 2 * (z-1). (Pensez à gcd(z, 1).)