Recherche:

N'y a-t-il pas \sum_{i=0}^{\log_2(n)} 2 {\lfloor}\frac{n}{2^i}{\rfloor}-1 itérations en tout ? Ce qui est égal à 4n - log_2(n) - 3 si on ne prend pas la partie entière, ce qui correspond à une...

donc la complexité sera inférieure a n*log n et je crois qu'elle doit être aussi supérieure a log^2n ?

quelle est la solution ?

je crois que ça sera log(logn)*n

la boucle a l’intérieur est exécutée 2n(1+1/2+1/2^2+1/2^3+1/2^4+...........+1/2^logn)

donc a quoi est égale cette somme ?

je voudrais vérifier si la complexité du bout de code suivant est nlogn ?


i=n
s=0
tq (i>0) faire
j = 2 * i
tq (j>1) faire
s=s+(j-i)*(s+1)
j = j-1