Existe-t-il un système derrière la magie de l'analyse algorithmique?

159

Il y a beaucoup de questions sur la façon d'analyser le temps d' exécution des algorithmes (voir, par exemple, l' et ). Beaucoup sont similaires, par exemple ceux qui demandent une analyse des coûts des boucles imbriquées ou des algorithmes de division et de conquête, mais la plupart des réponses semblent être faites sur mesure.

D'autre part, les réponses à une autre question générale expliquent la situation dans son ensemble (en particulier en ce qui concerne l'analyse asymptotique) avec quelques exemples, mais pas comment se salir les mains.

Existe-t-il une méthode générale structurée pour analyser le coût des algorithmes? Le coût peut être la durée d'exécution (complexité temporelle) ou une autre mesure de coût, telle que le nombre de comparaisons exécutées, la complexité d'espace ou autre chose.

Ceci est supposé devenir une question de référence pouvant être utilisée pour orienter les débutants; d'où sa portée plus large que d'habitude. Veillez à donner des réponses générales, présentées de manière didactique, illustrées par au moins un exemple, mais couvrant néanmoins de nombreuses situations. Merci!

Raphaël
la source
3
Merci aux auteurs de StackEdit d’ avoir rendu l’écriture de longs articles aussi pratique, et à mes lecteurs bêta , FrankW , Juho , Gilles et Sebastian, qui m’ont aidé à aplanir un certain nombre de failles dans les versions précédentes.
Raphaël
1
Hey @Raphael, c'est merveilleux. Je pensais que je suggérerais de le mettre en format PDF pour le faire circuler? Ce genre de chose pourrait devenir une référence vraiment utile.
Hadsed
1
@ hadsed: Merci, je suis content que cela vous soit utile! Pour le moment, je préfère qu'un lien vers ce post soit distribué. Cependant, le contenu de l'utilisateur SE est "licencié sous cc by-sa 3.0 avec attribution requise" (voir bas de page) afin que tout le monde puisse créer un fichier PDF à partir de cette attribution, à condition que l'attribution soit donnée.
Raphaël
2
Je ne suis pas particulièrement compétent en la matière, mais est-il normal qu'il n'y ait aucune référence au théorème maître dans aucune réponse?
Babou
1
@ Babou Je ne sais pas ce que «normal» signifie ici. De mon point de vue, le théorème maître n'a pas sa place ici: il s'agit d'analyser des algorithmes, le théorème maître est un outil très spécifique pour résoudre (certaines) récurrences (et très approximativement). Puisque les mathématiques ont été abordées ailleurs (par exemple ici ), j'ai choisi de ne couvrir ici que la partie de l'algorithme aux mathématiques. Je donne des références à des postes qui traitent du calcul mathématique dans ma réponse.
Raphaël

Réponses:

134

Traduire du code en mathématiques

Avec une sémantique opérationnelle (plus ou moins) formelle , vous pouvez traduire littéralement le code (pseudo-) d'un algorithme en une expression mathématique qui vous donne le résultat, à condition que vous puissiez manipuler l'expression sous une forme utile. Cela fonctionne bien pour les mesures de coût additives telles que le nombre de comparaisons, les échanges, les instructions, les accès à la mémoire, les cycles de certaines machines abstraites, etc.

Exemple: Comparaisons dans Bubblesort

Considérons cet algorithme qui trie un tableau donné A:

 bubblesort(A) do                   1
  n = A.length;                     2
  for ( i = 0 to n-2 ) do           3
    for ( j = 0 to n-i-2 ) do       4
      if ( A[j] > A[j+1] ) then     5
        tmp    = A[j];              6
        A[j]   = A[j+1];            7
        A[j+1] = tmp;               8
      end                           9
    end                             10
  end                               11
end                                 12

Supposons que nous voulions effectuer l'analyse de l'algorithme de tri habituel, à savoir compter le nombre de comparaisons d'éléments (ligne 5). Nous notons immédiatement que cette quantité ne dépend pas du contenu du tableau A, mais de sa longueur . Nous pouvons donc traduire littéralement les boucles (imbriquées) en sommes (imbriquées); la variable de boucle devient la variable de somme et la plage est reportée. On a:nfor

Ccmp(n)=i=0n2j=0ni21==n(n1)2=(n2) ,

où est le coût pour chaque exécution de la ligne 5 (que nous comptons).1

Exemple: échanges dans Bubblesort

Je noterai par le sous-programme qui consiste en lignes vers et par les coûts d'exécution de ce sous-programme (une fois).Pi,jijCi,j

Maintenant, disons que nous voulons compter les échanges , c’est la fréquence à laquelle est exécutée. Il s’agit d’un "bloc de base", c’est un sous-programme qui est toujours exécuté de manière atomique et a un coût constant (ici, ). La sous-traitance de ces blocs est une simplification utile que nous appliquons souvent sans réfléchir ni en parler. 1P6,81

Avec une traduction similaire à celle ci-dessus, nous arrivons à la formule suivante:

Cswaps(A)=i=0n2j=0ni2C5,9(A(i,j)) .

( i , j ) P 5 , 9A(i,j) indique l'état du tableau avant la -ième itération de .(i,j)P5,9

Notez que j'utilise au lieu de comme paramètre; on verra bientôt pourquoi. Je n’ajoute pas et tant que paramètres de car les coûts ne dépendent pas d’eux ici (dans le modèle de coûts uniformes , c’est-à-dire); en général, ils pourraient juste.n i j C 5 , 9AnijC5,9

Il est clair que les coûts de dépendent du contenu de (les valeurs et , plus précisément), nous devons donc en tenir compte. Nous sommes maintenant confrontés à un défi: comment "décompresser" ? Eh bien, nous pouvons rendre la dépendance sur le contenu de explicite: A C 5 , 9 AP5,9AA[j]A[j+1]C5,9A

C5,9(A(i,j))=C5(A(i,j))+{1,A(i,j)[j]>A(i,j)[j+1]0,else .

Pour tout tableau d'entrée donné, ces coûts sont bien définis, mais nous voulons un énoncé plus général. nous devons faire des hypothèses plus fortes. Laissez-nous enquêter sur trois cas typiques.

  1. Le pire des cas

    En regardant la somme et en notant que , nous pouvons trouver une limite supérieure triviale pour le coût:C5,9(A(i,j)){0,1}

    Cswaps(A)i=0n2j=0ni21=n(n1)2=(n2) .

    Mais cela peut-il arriver , c’est-à-dire qu’un est atteint pour cette limite supérieure? Il se trouve que oui: si nous entrons un tableau d’éléments distincts par paires inversement triés, chaque itération doit effectuer un swap¹. Par conséquent, nous avons calculé le nombre exact de swaps de Bubblesort dans le pire des cas .A

  2. Le meilleur des cas

    Inversement, il existe une limite inférieure triviale:

    Cswaps(A)i=0n2j=0ni20=0 .

    Cela peut aussi arriver: sur un tableau déjà trié, Bubblesort n'exécute pas un échange.

  3. Le cas moyen

    Le pire et le meilleur des cas ouvrent un fossé considérable. Mais quel est le nombre typique de swaps? Afin de répondre à cette question, nous devons définir ce que signifie "typique". En théorie, nous n'avons aucune raison de préférer une entrée à une autre et nous supposons donc généralement une distribution uniforme de toutes les entrées possibles, c'est-à-dire que chaque entrée est également probable. Nous nous limitons aux tableaux avec des éléments distincts par paires et supposons ainsi le modèle de permutation aléatoire .

    Ensuite, nous pouvons réécrire nos coûts comme ceci²:

    E[Cswaps]=1n!Ai=0n2j=0ni2C5,9(A(i,j))

    Nous devons maintenant aller au-delà de la simple manipulation des sommes. En examinant l'algorithme, nous constatons que chaque échange supprime exactement une inversion de (nous échangeons seulement les voisins³). Autrement dit, le nombre de swaps effectuées sur est exactement le nombre de retournements de . Ainsi, nous pouvons remplacer les deux sommes intérieures et obtenirAAinv(A)A

    E[Cswaps]=1n!Ainv(A) .

    Heureusement pour nous, il a été déterminé que le nombre moyen d’inversions est

    E[Cswaps]=12(n2)

    qui est notre résultat final. Notez que cela représente exactement la moitié du coût le plus défavorable.


  1. Notez que l'algorithme a été soigneusement formulé pour que "la dernière" itération avec i = n-1la boucle externe qui ne fait jamais rien ne soit pas exécutée.
  2. " " est une notation mathématique pour "valeur attendue", qui est juste la moyenne.E
  3. Nous apprenons en cours de route qu'aucun algorithme qui permute seulement les éléments voisins peut être asymptotiquement plus rapide que Bubblesort (même en moyenne) - le nombre d'inversions est une limite inférieure pour tous ces algorithmes. Ceci s'applique par exemple au tri par insertion et au tri par sélection .

La méthode générale

Nous avons vu dans l'exemple que nous devons traduire la structure de contrôle en mathématiques; Je présenterai un ensemble typique de règles de traduction. Nous avons également vu que le coût d'un sous-programme donné peut dépendre de l' état actuel , c'est-à-dire (approximativement) des valeurs actuelles des variables. Comme l'algorithme modifie (généralement) l'état, la méthode générale est un peu lourde à noter. Si vous commencez à vous sentir confus, je vous suggère de revenir à l'exemple ou de créer le vôtre.

Nous notons avec l’état actuel (imaginez-le comme un ensemble d’assignations de variables). Lorsque nous exécutons un programme qui commence dans l’état , nous nous retrouvons dans l’état (à condition que se termine).ψPψψ/PP

  • Déclarations individuelles

    S;Si vous ne qu'une seule déclaration , vous lui affectez des coûts . Ce sera généralement une fonction constante.CS(ψ)

  • Expressions

    Si vous avez une expression Ede la forme E1 ∘ E2(par exemple, une expression arithmétique pouvant être addition ou multiplication, vous additionnez les coûts de manière récursive:

    CE(ψ)=c+CE1(ψ)+CE2(ψ) .

    Notez que

    • le coût d'opération peut ne pas être constant mais dépend des valeurs de et etcE1E2
    • l'évaluation d'expressions peut changer l'état dans de nombreuses langues,

    vous devrez donc peut-être faire preuve de souplesse avec cette règle.

  • Séquence

    Étant donné un programme Psous forme de séquence de programmes Q;R, vous ajoutez les coûts à

    CP(ψ)=CQ(ψ)+CR(ψ/Q) .

  • Les conditions

    Étant donné un programme Pde la forme if A then Q else R end, les coûts dépendent de l'état:

    CP(ψ)=CA(ψ)+{CQ(ψ/A),A evaluates to true under ψCR(ψ/A),else

    En général, l’évaluation Apeut très bien changer l’état, d’où la mise à jour des coûts des différentes branches.

  • Boucles For

    Étant donné un programme Pdu formulaire for x = [x1, ..., xk] do Q end, attribuer des coûts

    CP(ψ)=cinit_for+i=1kcstep_for+CQ(ψi{x:=xi})

    où est l'état avant le traitement de la valeur , c'est-à-dire après l'itération avec étant défini sur , ..., .ψiQxixx1xi-1

    Notez les constantes supplémentaires pour la maintenance de la boucle; la variable de boucle doit être créée ( ) et attribuer ses valeurs ( ). Ceci est pertinent puisquecinit_forcstep_for

    • le calcul de la prochaine xipeut être coûteux et
    • une forboucle avec un corps vide (par exemple, après avoir simplifié dans le meilleur des cas avec un coût spécifique) n'a pas de coût nul si elle effectue des itérations.
  • Alors que les boucles

    Étant donné un programme Pdu formulaire while A do Q end, attribuer des coûts

    CP(ψ) =CA(ψ)+{0,A evaluates to false under ψCQ(ψ/A)+CP(ψ/A;Q), else

    En inspectant l'algorithme, cette récurrence peut souvent être bien représentée sous la forme d'une somme similaire à celle de for-loops.

    Exemple: considérons cet algorithme court:

    while x > 0 do    1
      i += 1          2
      x = x/2         3
    end               4
    

    En appliquant la règle, on obtient

    C1,4({i:=i0;x:=x0}) =c<+{0,x00c+=+c/+C1,4({i:=i0+1;x:=x0/2}), else

    avec des coûts constants, pour les instructions individuelles. Nous supposons implicitement que ceux-ci ne dépendent pas de l'état (les valeurs de et ); Cela peut être vrai ou non dans la "réalité": pensez aux débordements!cix

    Nous devons maintenant résoudre cette récurrence pour . Nous notons que ni le nombre d'itérations ni le coût du corps de la boucle ne dépendent de la valeur de , nous pouvons donc le supprimer. Il nous reste cette récurrence:C1,4i

    C1,4(x)={c>,x0c>+c+=+c/+C1,4(x/2), else

    Cela résout avec des moyens élémentaires de

    C1,4(ψ)=log2ψ(x)(c>+c+=+c/)+c> ,

    réintroduire symboliquement l'état complet; si , alors .ψ={,x:=5,}ψ(x)=5

  • Appels de procédure

    Étant donné un programme Pde la forme M(x)pour un paramètre (s) xMest une procédure avec paramètre (nommé) p, attribuer des coûts

    CP(ψ)=ccall+CM(ψglob{p:=x}) .

    Notez à nouveau la constante supplémentaire (qui peut en fait dépendre de !). Les appels de procédure sont coûteux en raison de la manière dont ils sont mis en œuvre sur de vraies machines, et dominent parfois même le temps d'exécution (par exemple, évaluer naïvement la récurrence des numéros de Fibonacci).ccallψ

    Je passe sous silence certaines questions sémantiques que vous pourriez avoir avec l'état ici. Vous voudrez faire la distinction entre l'état global et les appels locaux à la procédure. Supposons que nous ne transmettons état global ici et Mobtient un nouvel état local, initialisé en définissant la valeur de pla x. De plus, xpeut être une expression que nous supposons (généralement) être évaluée avant de la transmettre.

    Exemple: considérons la procédure

    fac(n) do                  
      if ( n <= 1 ) do         1
        return 1               2
      else                     3
        return n * fac(n-1)    4
      end                      5
    end                        
    

    Selon les règles, on obtient:

    Cfac({n:=n0})=C1,5({n:=n0})=c+{C2({n:=n0}),n01C4({n:=n0}), else=c+{creturn,n01creturn+c+ccall+Cfac({n:=n01}), else

    Notez que nous ne tenons pas compte de l'état global, car il est facclair qu'aucun accès à aucun. Cette récurrence particulière est facile à résoudre pour

    Cfac(ψ)=ψ(n)(c+creturn)+(ψ(n)1)(c+ccall)

Nous avons présenté les fonctionnalités linguistiques que vous rencontrerez dans un pseudo-code typique. Méfiez-vous des coûts cachés lorsque vous analysez un pseudo-code de haut niveau. en cas de doute, dépliez-vous. La notation peut sembler lourde et est certainement une question de goût; les concepts énumérés ne peuvent cependant pas être ignorés. Cependant, avec une certaine expérience, vous pourrez voir immédiatement quelles parties de l'état sont pertinentes pour quelle mesure de coût, par exemple la "taille du problème" ou le "nombre de sommets". Le reste peut être supprimé - cela simplifie considérablement les choses!

Si vous pensez maintenant que cela est beaucoup trop compliqué, être conseillé: il est ! Déduire les coûts exacts des algorithmes dans tout modèle si proche des machines réelles pour permettre des prédictions d'exécution (même relatives) est une tâche ardue. Et cela ne prend même pas en compte la mise en cache et autres effets pervers sur de vraies machines.

Par conséquent, l'analyse algorithmique est souvent simplifiée au point d'être mathématiquement traitable. Par exemple, si vous n'avez pas besoin de coûts exacts, vous pouvez surestimer ou sous-estimer à tout moment (pour les limites supérieures et inférieures): réduire l'ensemble des constantes, supprimer les conditions, simplifier les sommes, etc.

Une note sur le coût asymptotique

Ce que vous trouverez habituellement dans la littérature et sur le Web, c'est l'analyse "Big-Oh". Le terme approprié est l' analyse asymptotique , ce qui signifie qu'au lieu de calculer les coûts exacts comme nous l'avons fait dans les exemples, vous ne donnez les coûts que jusqu'à un facteur constant et dans la limite (grosso modo, "pour Big ").n

Ceci est (souvent) juste puisque les déclarations abstraites ont des coûts (généralement inconnus) en réalité, selon la machine, le système d'exploitation et d' autres facteurs, et à court runtimes peut être dominé par le système d'exploitation mise en place du processus en premier lieu et ainsi de suite. Donc, vous obtenez une perturbation, de toute façon.

Voici comment l'analyse asymptotique est liée à cette approche.

  1. Identifiez les opérations dominantes (qui induisent des coûts), c’est-à-dire les opérations qui se produisent le plus souvent (jusqu’à facteurs constants). Dans l'exemple Bubblesort, un choix possible est la comparaison de la ligne 5.

    Vous pouvez également lier toutes les constantes des opérations élémentaires à leur maximum (en haut), respectivement. leur minimum (par le bas) et effectuer l’analyse habituelle.

  2. Effectuez l'analyse en utilisant les comptes d'exécution de cette opération en tant que coût.
  3. Lors de la simplification, autorisez les estimations. Veillez à ne permettre les estimations à partir d'en haut que si votre objectif est une limite supérieure ( ), respectivement. d'en bas si vous voulez des limites inférieures ( ).OΩ

Assurez-vous de bien comprendre la signification des symboles Landau . Rappelez-vous que de telles limites existent pour les trois cas ; utiliser n'implique pas une analyse dans le pire des cas.O

Lectures complémentaires

L'analyse des algorithmes présente de nombreux défis et astuces. Voici quelques lectures recommandées.

Il existe de nombreuses questions liées qui utilisent des techniques similaires à celle-ci.

Raphaël
la source
1
peut-être quelques références et exemples au théorème maître (et à ses extensions ) pour l'analyse asymptotique
Nikos M.
@NikosM C'est hors de portée ici (voir aussi les commentaires sur la question ci-dessus). Notez que je renvoie à notre article de référence sur la résolution des récurrences, qui présente Master théorem et al.
Raphaël
@ Nikos M: mon 0,02 $: bien que le théorème principal fonctionne pour plusieurs récurrences, il ne le sera pas pour beaucoup d'autres; il existe des méthodes standard pour résoudre les récidives. Et il existe des algorithmes pour lesquels nous n'aurons même pas de récurrence donnant le temps d'exécution; certaines techniques de comptage avancées peuvent être nécessaires. Pour ceux qui ont de bonnes connaissances en mathématiques, je suggère l'excellent livre de Sedgewick et Flajolet, "Analysis of Algorithms", qui contient des chapitres tels que "relations de récurrence", "fonctions génératrices" et "approximations asymptotiques". Les structures de données apparaissent à titre d'exemples occasionnels et l'accent est mis sur les méthodes!
Jay
@Raphael Je ne trouve aucune mention sur le Web pour cette méthode "Traduire du code en mathématiques" basée sur la sémantique opérationnelle. Pouvez-vous citer un livre, un article ou un article traitant plus formellement de cette question?. Ou dans le cas où cela a été développé par vous, avez-vous quelque chose de plus en profondeur?
Wyvern666
1
@ Wyvern666 Malheureusement, non. Je l'ai inventé moi-même, pour autant que quiconque puisse prétendre inventer quelque chose comme ça. Peut-être que j'écrirai moi-même un ouvrage à citer. Ceci dit, tout le corpus de travail autour de la combinatoire analytique (Flajolet, Sedgewick et bien d’autres) en est le fondement. La plupart du temps, ils ne s'embarrassent pas de la sémantique formelle de "code", mais ils fournissent les bases mathématiques nécessaires pour gérer les coûts additifs des "algorithmes" en général. Honnêtement, je pense que les concepts présentés ici ne sont pas très profonds - les mathématiques dans lesquelles vous pouvez entrer sont cependant.
Raphaël
29

Nombre de déclarations d'exécution

Il y a une autre méthode, défendue par Donald E. Knuth dans sa série The Art of Computer Programming . Contrairement à la traduction de l'ensemble de l'algorithme en une seule formule , il fonctionne indépendamment de la sémantique du code du côté "assembler les objets" et permet de passer à un niveau inférieur uniquement lorsque cela est nécessaire, en partant d'une vue "d'aigle". Chaque affirmation peut être analysée indépendamment des autres, ce qui conduit à des calculs plus clairs. Cependant, la technique se prête bien à un code assez détaillé, pas à un pseudo-code de niveau supérieur.

La méthode

C'est assez simple en principe:

  1. Attribuez un nom / numéro à chaque déclaration.
  2. Attribuez à chaque déclaration un coût .SiCi
  3. Déterminez pour chaque instruction son nombre d'exécutions .Siei
  4. Calculer les coûts totaux

    C=ieiCi .

Vous pouvez insérer des estimations et / ou des quantités symboliques à tout moment, ce qui affaiblit resp. généraliser le résultat en conséquence.

Sachez que l’étape 3 peut être arbitrairement complexe. C'est généralement là que vous devez travailler avec des estimations (asymptotiques) telles que " " pour obtenir des résultats.e77O(nlogn)

Exemple: recherche en profondeur d'abord

Considérez l'algorithme de traversée de graphique suivant:

dfs(G, s) do
  // assert G.nodes contains s
  visited = new Array[G.nodes.size]     1
  dfs_h(G, s, visited)                  2
end 

dfs_h(G, s, visited) do
  foo(s)                                3
  visited[s] = true                     4

  v = G.neighbours(s)                   5
  while ( v != nil ) do                 6
    if ( !visited[v] ) then             7
      dfs_h(G, v, visited)              8
    end
    v = v.next                          9
  end
end

Nous supposons que le graphe (non dirigé) est donné par des listes de contiguïté sur les nœuds . Soit le nombre d'arêtes.{0,,n1}m

En regardant simplement l'algorithme, nous voyons que certaines instructions sont exécutées aussi souvent que d'autres. Nous introduisons quelques espaces réservés , et pour les compteurs d'exécution :ABCei

i123456789eiAABBBB+CCB1C

En particulier, car chaque appel récursif de la ligne 8 provoque un appel de la ligne 3 (le premier étant causé par l'appel d'origine ). De plus, car la condition doit être vérifiée une fois par itération, puis une fois de plus afin de la quitter.e8=e31foodfse6=e5+e7while

Il est clair que . Maintenant, lors d’une preuve de correction, nous montrerons qu’il est exécuté exactement une fois par noeud; c'est-à-dire que . Mais ensuite, nous parcourons chaque liste d'adjacence exactement une fois et chaque bord implique deux entrées au total (une pour chaque nœud incident); nous obtenons itérations au total. En utilisant cela, nous dérivons le tableau suivant:A=1fooB=nC=2m

i123456789ei11nnn2m+n2mn12m

Cela nous conduit à des coûts totaux de exactement

C(n,m)=(C1+C2C8)+ n(C3+C4+C5+C6+C8)+ 2m(C6+C7+C9).

En instanciant des valeurs appropriées pour le nous pouvons obtenir des coûts plus concrets. Par exemple, si nous voulons compter les accès à la mémoire (par mot), nous utiliserionsCi

i123456789Cin00110101

et obtenir

Cmem(n,m)=3n+4m .

Lectures complémentaires

Voir au bas de mon autre réponse .

Raphaël
la source
8

L’analyse algorithmique, comme la démonstration de théorèmes, est en grande partie un art (par exemple, il existe des programmes simples (comme le problème de Collatz ) que nous ne savons pas analyser). Nous pouvons convertir un problème de complexité d’algorithme en problème mathématique, comme l’a expliqué de manière exhaustive Raphaël , mais pour pouvoir exprimer une limite sur le coût d’un algorithme en termes de fonctions connues, il nous reste à:

  1. Utilisez les techniques que nous connaissons des analyses existantes, telles que la recherche de bornes basées sur des récurrences que nous comprenons ou la somme / intégrales que nous pouvons calculer.
  2. Changez l'algorithme en quelque chose que nous savons analyser.
  3. Proposez une approche totalement nouvelle.
Ari Trachtenberg
la source
1
Je suppose que je ne vois pas en quoi cela ajoute quelque chose d’utile et de nouveau, au-delà des autres réponses. Les techniques sont déjà décrites dans d'autres réponses. Cela me semble plus un commentaire qu'une réponse à la question.
DW
1
J'ose dire que les autres réponses prouvent que ce n'est pas un art. Vous ne pourrez peut-être pas le faire (c.-à-d. Les mathématiques), et une certaine créativité (quant à l'application des mathématiques connues) pourra être nécessaire même si vous l'êtes, mais cela est vrai pour n'importe quelle tâche. Je suppose que nous n'aspirons pas à créer de nouvelles mathématiques ici. (En fait, cette question et ses réponses visaient à démystifier tout le processus.)
Raphael
4
@Raphael Ari parle de créer une fonction reconnaissable comme limite, plutôt que «le nombre d'instructions exécutées par le programme» (qui correspond à votre réponse). Le cas général est un art - il n'y a pas d'algorithme qui puisse créer une borne non triviale pour tous les algorithmes. Le cas courant, cependant, est un ensemble de techniques connues (comme le théorème maître).
Gilles
@Gilles Si tout ce pour quoi il n’existait aucun algorithme était un art, les artisans (en particulier les programmeurs) seraient mieux payés.
Raphaël
1
@AriTrachlenberg souligne un point important, il existe une multitude de façons d'évaluer la complexité temporelle d'un algorithme. Les définitions de la notation Big O elles-mêmes suggèrent ou énoncent directement leur nature théorique en fonction de l'auteur. "Le pire scénario" laisse clairement la place à la conjecture et à de nouveaux faits parmi tous les N en discussion. Sans parler de la nature même des estimations asymptotiques étant quelque chose de ... bien inexact.
Brian Ogden