Je ne peux pas comprendre la complexité temporelle de l'extrait de code suivant:

void  f( int N ){
   sum ++;
   if ( N   > 1){
      f( N /2);
      f( N /2);
   }

C'est la double itération qui me pose des problèmes.

Je sais (ou pense) que la complexité temporelle de

void  f( int N ){
   sum ++;
   if ( N   > 1){
      f( N /2);
   }

Est ~ log2 (N) mais je ne sais pas quoi faire avec l'autre code.

0
Gwen_vere 17 août 2017 à 14:22

2 réponses

Ce code est très similaire à traversée d'arbre binaire ,

void  f( int N ){
   sum ++;
   if ( N   > 1){
      f( N /2);  //like Traverse left subtree
      f( N /2);  //like Traverse right subtree
   }

Qui traverse essentiellement chaque nœud une fois, avec une complexité temporelle O(N).

                    n/8
             n/4   --------- 
                    n/8
      n/2   ------------------    

                    n/8
             n/4  ---------
                    n/8

n -------------------------------
                    n/8
             n/4    --------- 
                    n/8
      n/2   ----------------

                    n/8
             n/4   ---------
                    n/8

Cela continue jusqu'à ce que la valeur passée devienne 1 ou 0.

0
Saurav Sahu 17 août 2017 à 11:54

Un bon moyen de résoudre ce problème serait:


1. Recherche de la relation de récurrence

Pour chaque appel à f, nous avons une complexité temporelle T(N). Chaque appel contient:

  • Un travail constant C: sum++, comparaison N > 1, surcharge d'appel récursif, etc.
  • 2 appels récursifs à f, chacun avec une complexité temporelle T(N / 2).

Ainsi la relation de récurrence est donnée par T(N) = 2T(N/2) + C.


2. Trouver une solution par inspection

Si nous substituons à plusieurs reprises T(N) en lui-même, nous pouvons voir un modèle émergent:

enter image description here

Quelle est la limite supérieure de la somme, m? Puisque la condition d'arrêt est N > 1, après des substitutions répétées, l'exigence serait

enter image description here

Ainsi la somme est égale (en supprimant l'arrondi, et la constante C car elle est simplement multiplicative):

enter image description here


3. Preuve par induction

  • Étape de base: testez si le résultat de la somme est correct pour la valeur la plus basse possible de N, soit 2:

    entrez la description de l'image ici

    Le résultat est cohérent.

  • Étape de récurrence: confirmez que si la somme est correcte pour N / 2, elle l'est également pour N:

    entrez la description de l'image ici

    C'est exactement notre relation de récurrence d'origine.

Donc par récurrence, le résultat de la sommation est correct, et T(N) est bien Ө(N).


4. Test numérique:

Nous pouvons écrire du code pour confirmer notre résultat si nécessaire:

function T(n) {
  return n > 1 ? 2 * T(floor(n/2)) + 1 : 1;
}

Résultats:

N           T(N)
-------------------------
2           3
4           7
8           15
16          31
32          63
64          127
128         255
256         511
512         1023
1024        2047
2048        4095
4096        8191
8192        16383
16384       32767
32768       65535
65536       131071
131072      262143
262144      524287
524288      1048575
1048576     2097151
2097152     4194303
4194304     8388607
8388608     16777215
16777216    33554431
33554432    67108863
67108864    134217727
134217728   268435455
268435456   536870911
536870912   1073741823
1073741824  2147483647

Graphique:

enter image description here

3
meowgoesthedog 17 août 2017 à 12:18