8
votes

Complexité pour les boucles imbriquées divisant par 2

J'essaie de comprendre la complexité d'A pour la boucle en utilisant la grosse notation. Je l'ai déjà fait dans mes autres classes, mais celle-ci est plus rigoureuse que les autres parce que c'est sur l'algorithme réel. Le code est le suivant:

for(i=n ; i>1 ; i/=2) //for any size n
{
    for(j = 1; j < i; j++)
    {
      x+=a
    }
}

c loops big-o

23 commentaires

Comment pouvez-vous simplifier la somme n + n / 2 + n / 4 + ... ?


                                        
                                                                            @Olicharlesworth Je ne comprends pas comment  n + n / 2 + n / 4 + ...  est égal à  nlogn 

                                        
                                                                            @ Rüppell'svulture: Ce n'est pas le cas.
                                        
                                                                            @Grijeshchauhanhan alors pourquoi deux upvotes pour le premier commentaire?
                                        
                                                                            @ Rüppell'svulture: vraisemblablement parce que certaines personnes pensaient (incorrectement) que c'était la bonne réponse.
                                        
                                                                            @Olicharlesworth Quelle est l'approximation de  n + n / 2 + n / 4 ....  alors? Mes mathématiques sont pauvres, mais je sens toujours que c'est  n + logn 

                                        
                                                                            @ Rüppell'svulture: si  n  est une puissance de deux, alors c'est exactement  2n-1 .

                                        
                                                                            @Olicharsworth pourquoi pas (log (n) ^ (2 ^ (log (n) +1))) -1 = O (n)
                                        
                                                                            @Waldhomaana: hein? Comment cette expression se rapportait-elle à cela?
                                        
                                                                            @OlichaLLAlesworth Désolé, je veux dire que vous décrémentez la boucle extérieure I en plongeant par 2, et dans la boucle interne, vous exécutez I fois, le nombre d'itérations sera donc une somme sur tous les pouvoirs de deux moins ou égaux à n, plus que 0, qui est n ^ (log (n) +1) - 1, so (n).
                                        
                                                                            @Olicharlesworth Si c'est  O (n) , il est également  O (n * journal n) , donc ce n'est pas  mauvais .

                                        
                                                                            @Olicharlesworth Normalement lors du calcul de O (Bigoh), vous n'avez pas besoin de trop de détails. mais ia en classe j'ai besoin de tous les détails pour mes examens
                                        
                                                                            @Olicharlesworth est  2N-1 = N + N / 2 + N / 4 ......  Une formule de la série? Maths de base?

                                        
                                                                            @ Rüppell'svulture:  en.wikipedia.org/wiki/geometric_series#sum .
                                        
                                                                            @Danielfischer est journal (n) très moins comparé à  n  quand  n  est grand et peut donc être ignoré? C'est pourquoi  O (n) = O (n * logn) ?

                                        
                                                                            @ Rüppell'svulture: Il fait allusion au fait que O (n) est un sous-ensemble de O (n log n). (C'est-à-dire une fonction asymptotiquement délimitée par-dessus par  k.n  est également délimitée par  k.n.log (n) .)

                                        
                                                                            @ Rüppell'svulture Les deux classes  O (n)  et  O (n * journal n)  sont différents, mais  o (n)  est un Soublisses de  O (n * journal n)  (et de  O (n²) ,  o (2 ^ n) ,  o ( n!) ). Si vous avez une limite supérieure  f (n) , chaque fonction  plus grande  est également une limite supérieure, donc si  boucle (n) <= c * n , qui dit que  boucle  est dans  o (n) , puis de manière triviale  boucle (n) <= c * n * log n  pour  n> = base_of_log , et donc  boucle  est également dans  O (n * journal n) .

                                        
                                                                            @Danielfischer Je suis botifking Cette question de sorte que une fois que j'ai terminé un livre sur des algorithmes, ce que vous avez dit fera un sens complet pour moi !!
                                        
                                                                            @Daniel Fischer Quelle est votre complexité du problème?
                                        
                                                                            @Waldhomaana  o (n)  est la limite tranchante. Comme indiqué ci-dessus, chaque fonction plus grande fournirait également une limite supérieure correcte, mais ce ne serait pas tranchant. La boucle est  θ (n) , ce qui signifie que le nombre d'itérations est limitée de ci-dessous par un multiple constant de  N , et de ci-dessus,  c * n <= loop_itérations (n) <= c * n  pour certains  0 .

                                        
                                                                            ce moyen de compexité pour cela it O (n) ??
                                        
                                                                            @Olicharlesworth  math.stackexchange.com/questions/401937/... 
                                        
                                                                            Lorsque l'incrément / décrémentation d'une boucle est multiplication / division, nous disons que c'est une boucle logarithmique.

3 Réponses : 3 votes Le nombre total d'itérations de la boucle interne est N + N / 2 + N / 4 + ... + 1 qui est d'environ 2n. Donc la complexité est O (n). 0 commentaires 3 votes La complexité doit être O (n) . Il forme une série géométrique (pas exactement mais approximativement). La boucle fonctionne pour n + n / 2 + n / 4 + .... +1 qui est environ 2n . et O (2n) = O (n) . 0 commentaires 4 votes Pour résoudre formellement la complexité de votre algorithme de votre algorithme, vous pouvez utiliser les étapes suivantes avec la notation Sigma: Aussi, jetez un coup d'œil une dernière diapositive de ce très intéressant Document par le Dr Jauhar. 0 commentaires

Articles qui pourrait vous intéresser : Que puis-je utiliser pour la conversion d'entrée au lieu de scanf? Comment puis-je calculer a * b / c lorsque a et b sont tous deux plus petits que c, mais que a * b déborde? Comment vérifier si un pointeur void (void *) est l'un des deux types de données? L'écran LCD affiche des caractères aléatoires (MPLAB)