Exemples : Déterminer Big O

Cette section donne plusieurs exemples de détermination du Big O pour les instructions de répétition, de séquence et de sélection.

Exemple 1

Considérez la complexité temporelle de la boucle suivante :

pour (int i = 1; i <= n; i++) {
k = k + 5;
}

C'est un temps constant, c, pour l'exécution

k = k + 5;

Puisque la boucle est exécutée n fois, la complexité temporelle de la boucle est

T(n) = (une constante c)*n = O(n).

L'analyse théorique prédit les performances de l'algorithme. Pour voir comment cet algorithme fonctionne, nous exécutons le code dans le programme ci-dessous pour obtenir le temps d'exécution pour n = 1000000, 10000000, 100000000 et 100000000.

Notre analyse prédit une complexité temporelle linéaire pour cette boucle. Comme le montre l’exemple de sortie, lorsque la taille d’entrée augmente 10 fois, le temps d’exécution augmente environ 10 fois. L'exécution confirme la prédiction.

Exemple 2

Quelle est la complexité temporelle de la boucle suivante ?

pour (int i = 1; i <= n; i++) {
pour (int j = 1; j <= n; j++) {
k = k + je + j;
}
}

C'est un temps constant, c, pour l'exécution

k = k + i + j;

La boucle externe s'exécute n fois. Pour chaque itération dans la boucle externe, la boucle interne est exécutée n fois. Ainsi, la complexité temporelle de la boucle est de

T(n) = (une constante c)*n*n = O(n^2)

Un algorithme avec une complexité temporelle O(n^2) est appelé unalgorithme quadratiqueet il présente un taux de croissance quadratique. L’algorithme quadratique se développe rapidement à mesure que la taille du problème augmente. Si vous doublez la taille d’entrée, le temps d’exécution de l’algorithme est quadruplé. Les algorithmes avec une boucle imbriquée sont souvent quadratiques.

Exemple 3

Considérez la boucle suivante :

pour (int i = 1; i <= n; i++) {
pour (int j = 1; j <= i; j++) {
k = k + je + j;
}
}

La boucle externe s'exécute n fois. Pour i = 1, 2, c , la boucle interne est exécutée une fois, deux fois et n fois. Ainsi, la complexité temporelle de la boucle est de

Exemple 4

Considérez la boucle suivante :

pour (int i = 1; i <= n; i++) {
pour (int j = 1; j <= 20; j++) {
k = k + je + j;
}
}

La boucle interne s'exécute 20 fois et la boucle externe n fois. Par conséquent, la complexité temporelle de la boucle est de

T(n) = 20*c*n = O(n)

Exemple 5

Considérez les séquences suivantes :

pour (int j = 1; j <= 10; j++) {
k = k + 4;
}

pour (int i = 1; i <= n; i++) {
pour (int j = 1; j <= 20; j++) {
k = k + je + j;
}
}

La première boucle s'exécute 10 fois et la deuxième boucle 20 * n fois. Ainsi, la complexité temporelle de la boucle est de

T(n) = 10*c + 20*c*n = O(n)

Exemple 6

Considérez la déclaration de sélection suivante :

if (list.contains(e)) {
System.out.println(e);
}
sinon
pour (Objet t : liste) {
System.out.println(t);
}

Supposons que la liste contienne n éléments. Le temps d'exécution pourlist.contains(e)est O(n). La boucle dans la clauseelseprend un temps O(n). Par conséquent, la complexité temporelle de l’ensemble de la déclaration est de

Exemple 7

Considérons le calcul de a^n pour un entier n. Un algorithme simple multiplierait n fois, comme suit :

résultat = 1;
pour (int i = 1; i <= n; i++)
résultat *= a;

L'algorithme prend un temps O(n). Sans perte de généralité, supposons n = 2^k. Vous pouvez améliorer l'algorithme en utilisant le schéma suivant :

résultat = a;
pour (int i = 1; i <= k; i++)
résultat = résultat * résultat ;

L'algorithme prend un temps O(logn). Pour un n arbitraire, vous pouvez réviser l'algorithme et prouver que la complexité est toujours O(logn).

Pour simplifier, puisque 0(logn) = 0(log2n) = 0(logan), la base constante est omise.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!