Complexité temporelle des paires dans une double boucle de tableau

Question

Je sais que ce qui suit est: o (n ^ 2) ,

int count = 0;
for(int i = 0; i<array.length(); i++) {
   for(int j = i+1; j<array.length(); j++) {
       if(array[i] == array[j]) {
           count = count + 1;
       }
   }
}

mais, devrait-il être pris en compte quelque chose comme count = count + 1;? Pour prédire ou constituer une équation de temps complexe, ou utiliser la notation de somme,

n + n-1 + n-2 + n-3 + (…) + 1

Answer 1

C'est une tâche bien connue "Vérification des doublons" et vous pouvez le trouver par exemple dans Tim Fursgarden - algorithmes illuminated_ Partie 1_ La base - (2017) 42 page. Permettez-moi de dire que, comme ici, donc dans le livre prenant dernier index "i" comme $ n= $ "gray.length ()" n'a aucun sens, car alors index " J "manque de frontières. Mais cela n'affecte pas notre comptage.

Comme toujours principal est de choisir le fonctionnement pour le compte - ici son "compte= compte + 1". Évidemment, le meilleur cas, c'est-à-dire une moindre quantité d'opérations, est $ 0 $ . Et pire un cas, c'est-à-dire une quantité maximale d'opérations, est la somme (je corrige-la donc de prendre en conséquence indice "i" up $ n-1 $ ) apporté par vous $ t (n)= 1 + 2 + \ CDOTS + (n-1)=frac {n (n-1)} {2} $ (nous considérons le cas $ n \ geqslant 2 $ ).

maintenant, parce que $ \ frac {n (n-1)} {2} \ Leqslant \ frac {n \ cdot 2n} {2}= n ^ 2 $ , il est facile de conclure, ce pire case $ t (n) \ in o (n ^ 2) $ .

.

Answer 2

La complexité temporelle d'un algorithme dépend du modèle de calcul.Les algorithmes sont généralement analysés dans la machine RAM, dans laquelle les opérations de base sur des mots de la machine (telles que l'attribution, l'arithmétique et la comparaison) coûtent $ O (1) $ .Un mot de la machine a une longueur $ o (\ journal n) $ , où $ n $ est la taille del'entrée.

Dans votre cas, la taille de l'entrée est au moins $ n $ (défini comme la longueur de gen 100odiceTagCode), et donc array s'adapte dans une seule machinemot.Chacune des opérations de base de l'algorithme coûte $ O (1) $ , et la complexité de temps globale est donc $ \ theta(n ^ 2) $ , puisque l'algorithme exécute ces nombreuses opérations de base.