Big-O complexité d’un morceau de code

J’ai une question dans la conception des algorithmes sur la complexité. Dans cette question, un morceau de code est donné et je devrais calculer la complexité de ce code. Le pseudo-code est:

for(i=1;i<=n;i++){ j=i do{ k=j; j = j / 2; }while(k is even); } 

J’ai essayé cet algorithme pour certains nombres. et j’ai obtenu des résultats différents. par exemple si n = 6 cette sortie de l’algorithme est comme ci-dessous

 i = 1 -> executes 1 time i = 2 -> executes 2 times i = 3 -> executes 1 time i = 4 -> executes 3 times i = 5 -> executes 1 time i = 6 -> executes 2 times 

Il n’a pas de thème régulier, comment dois-je calculer cela?

    La limite supérieure donnée par les autres réponses est en réalité trop élevée. Cet algorithme a un runtime O (n), qui est une limite supérieure à O (n * logn).

    Preuve: Comptons combien d’itérations totales la boucle interne effectuera.

    La boucle externe est exécutée n fois. La boucle interne s’exécute au moins une fois pour chacun de ceux-ci.

    • Même pour i , la boucle interne s’exécute au moins deux fois. Cela arrive n/2 fois.
    • Pour i divisible par 4, la boucle interne s’exécute au moins trois fois. Cela arrive n/4 fois.
    • Pour i divisible par 8, la boucle interne s’exécute au moins quatre fois. Cela arrive n/8 fois.

    Ainsi, le nombre total de fois que la boucle interne s’exécute est:

     n + n/2 + n/4 + n/8 + n/16 + ... <= 2n 

    La quantité totale d'itérations de la boucle interne est comprise entre n et 2n , c'est-à-dire que c'est Θ (n).

    Vous supposez toujours que vous obtenez le pire scénario dans chaque niveau.
    maintenant, vous parcourez un tableau avec N éléments, nous commençons donc par O(N) .
    Maintenant, disons que votre i est toujours égal à X et X est toujours égal (souvenez-vous, pire des cas à chaque fois).
    combien de fois vous devez diviser X par 2 pour obtenir 1 ? (qui est la seule condition pour que les nombres pairs arrêtent la division quand ils atteignent 1).
    en d’autres termes, nous devons résoudre l’équation X/2^k = 1 qui est X=2^k et k=log<2>(X) cela fait prendre à notre algorithme O(n log<2>(X)) étapes, qui peuvent facilement être écrites comme O(nlog(n))

    Pour une telle boucle, nous ne pouvons pas séparer le nombre de boucles internes et externes – les variables sont serrées!

    Nous devons donc compter toutes les étapes.

    En fait, pour chaque itération de la boucle externe (sur i ), nous aurons

     1 + v_2(i) steps 

    v_2 est la valorisation 2-adique (voir par exemple: http://planetmath.org/padicvaluation ) qui correspond à la puissance de 2 dans la décomposition en facteur premier de i .

    Donc, si nous ajoutons des étapes pour tous, nous obtenons un nombre total d’étapes de:

     n_steps = \sum_{i=1}^{n} (1 + v_2(i)) = n + v_2(n!) // since v_2(i) + v_2(j) = v_2(i*j) = 2n - s_2(n) // from Legendre formula (see http://en.wikipedia.org/wiki/Legendre%27s_formula with `p = 2`) 

    On voit alors que le nombre de pas est exactement :

     n_steps = 2n - s_2(n) 

    Comme s_2(n) est la sum des chiffres de n dans la base 2 , il est négligeable (au plus log_2(n) car le chiffre dans la base 2 est 0 ou 1 et comme il y a au plus log_2(n) chiffres) n .

    La complexité de votre algorithme est donc équivalente à n :

     n_steps = O(n) 

    ce qui n’est pas le O(nlog(n)) indiqué dans beaucoup d’autres solutions mais une plus petite quantité!

    Commençons par le pire des cas:

    Si vous continuez à diviser avec 2 (intégrale), vous n’avez pas besoin de vous arrêter jusqu’à ce que vous arriviez à 1. Fondamentalement, le nombre de pas dépend de la largeur de bit, ce que vous découvrirez en utilisant le logarithme de deux. donc la partie interne est log n. la partie extérieure est évidemment n, donc N log N total.

    Une boucle do moitié j jusqu’à ce que k devienne impair. k est initialement une copie de j qui est une copie de i , donc lance 1 + puissance de 2 qui divise i :

    • i = 1 est impair, donc il fait 1 boucle de traversée,
    • i = 2 divise par 2 une fois, donc 1 + 1,
    • i = 4 divise deux fois par 2, donc 1 + 2, etc.

    Cela fait au plus 1 + log (i) do exécutions (logarithme avec base 2).

    La boucle for itère de 1 à n , donc la borne supérieure est n fois (1 + log n), qui est O (n log n).