Discussion :

[lyess]

J'ai une autre Algorithme si vous permettez :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Algo()
 
i=2;
tantque (i<N)
   faire
       i=i*i;
   fait;

_________________________________________________________________
Ma Solution:
J'ai déroulé pour N=17

i=2
i=4
i=16
i=(16)²

On aura une suite de la forme:
2 + 4 + 16 + (16)² + ... + k² \ tel que k<N

Mais cette suite est de raison (i-1) elle est ni géométrique ni autre!

Comment calculer sa complexité SVP ?

[souviron34]

tu es borné par sqrt(N)

[lyess]

tu es borné par sqrt(N)

sqrt(N)? Pas compris souviron34... La complexité est de combien?

[lagnon13]

sqrt(N)? Pas compris souviron34... La complexité est de combien?

Lorsque on a envie de s'asseoir c'est là qu'on voit l'importance des fesses

[tesla]

sqrt(N)? Pas compris souviron34... La complexité est de combien?

Sqrt c'est Square Root en Anglais, autrement dit la Racine Carrée.
Ton algo est borné par la fonction Racine Carrée.
-> Il croit de la "même façon" que la courbe de la Racine Carrée

[Invité]

Bonsoir,

tu es borné par sqrt(N)

Largement borné même !

On peut effectuer la décomposition suivante :

iteration |   1   |   2   |   3   |     4     |        k
  (i*i)   | (2*2) | (4*4) |(16*16)| (256*256) |       ...
          |       |       |       |           |    k-1      k-1
          | 1   1 | 2   2 | 4   4 |   8    8  |   2        2
    =     |2 * 2  |2 * 2  |2 * 2  |  2  * 2   |  2    *   2   

On obtient donc une complexité en O(log2(log2(N))