algorithm
Notation Big-O

Remarques

Une boucle simple

La fonction suivante trouve l'élément maximal dans un tableau:

int find_max(const int *array, size_t len) {
    int max = INT_MIN;
    for (size_t i = 0; i < len; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

La taille d'entrée est la taille du tableau, que j'ai appelée len dans le code.

Comptons les opérations.

int max = INT_MIN;
size_t i = 0;

Ces deux affectations ne sont effectuées qu’une seule fois, c’est donc 2 opérations. Les opérations en boucle sont les suivantes:

if (max < array[i])
i++;
max = array[i]

Comme il y a 3 opérations dans la boucle et que la boucle est effectuée n fois, nous ajoutons 3n à nos 2 opérations déjà existantes pour obtenir 3n + 2 . Donc, notre fonction prend 3n + 2 opérations pour trouver le max (sa complexité est 3n + 2 ). C'est un polynôme où le terme de croissance le plus rapide est un facteur de n, donc il est O (n).

Vous avez probablement remarqué que "l'opération" n'est pas très bien définie. Par exemple, j'ai dit que if (max < array[i]) était une opération, mais en fonction de l'architecture, cette instruction peut compiler par exemple trois instructions: une lecture de mémoire, une comparaison et une branche. J'ai également considéré toutes les opérations comme identiques, même si, par exemple, les opérations de mémoire seront plus lentes que les autres et que leurs performances varieront énormément, par exemple en raison des effets de cache. J'ai aussi complètement ignoré la déclaration de retour, le fait qu'une image sera créée pour la fonction, etc. Finalement, l'analyse de la complexité n'a pas d'importance, car peu importe comment je compte les opérations, cela ne changera que le coefficient. du facteur n et de la constante, le résultat sera toujours O (n). La complexité montre comment l'algorithme s'adapte à la taille de l'entrée, mais ce n'est pas le seul aspect des performances!

Une boucle imbriquée

La fonction suivante vérifie si un tableau a des doublons en prenant chaque élément, puis effectue une itération sur l'ensemble du tableau pour voir si l'élément est présent

_Bool contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len; j++) {
            if (i != j && array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

La boucle interne effectue à chaque itération un nombre d'opérations constant avec n . La boucle externe effectue également quelques opérations constantes et exécute la boucle interne n fois. La boucle externe elle-même est exécutée n fois. Donc, les opérations à l'intérieur de la boucle interne sont exécutées n^2 fois, les opérations dans la boucle externe sont exécutées n fois et l'affectation à i est effectuée une fois. Ainsi, la complexité sera quelque chose comme an^2 + bn + c , et comme le terme le plus élevé est n^2 , la notation O(n^2) est O(n^2) .

Comme vous l'avez peut-être remarqué, nous pouvons améliorer l'algorithme en évitant de faire les mêmes comparaisons plusieurs fois. Nous pouvons commencer à partir de i + 1 dans la boucle interne, car tous les éléments qui l'ont précédé auront déjà été vérifiés par rapport à tous les éléments du tableau, y compris celui de l'index i + 1 . Cela nous permet de laisser tomber la vérification i == j .

_Bool faster_contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if (array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

De toute évidence, cette deuxième version fait moins d'opérations et est donc plus efficace. Comment cela se traduit-il par la notation Big-O? Eh bien, le corps de la boucle interne est maintenant exécuté 1 + 2 + ... + n - 1 = n(n-1)/2 fois. C'est toujours un polynôme du deuxième degré, et il en est toujours de même pour O(n^2) . Nous avons clairement réduit la complexité, puisque nous avons divisé par 2 approximativement le nombre d'opérations que nous effectuons, mais nous sommes toujours dans la même classe de complexité que celle définie par Big-O. Afin de réduire la complexité à une classe inférieure, il faudrait diviser le nombre d'opérations par quelque chose qui tend vers l'infini avec n .

Un exemple O (log n)

introduction

Considérez le problème suivant:

L est une liste triée contenant n entiers signés ( n étant assez grand), par exemple [-5, -2, -1, 0, 1, 2, 4] (ici, n vaut 7). Si L est connu pour contenir le nombre entier 0, comment pouvez-vous trouver l'index de 0?

Approche naïve

La première chose qui me vient à l'esprit est de lire chaque index jusqu'à ce que 0 soit trouvé. Dans le pire des cas, le nombre d'opérations est n , la complexité est donc O (n).

Cela fonctionne très bien pour les petites valeurs de n , mais existe-t-il un moyen plus efficace?

Dichotomie

Considérons l'algorithme suivant (Python3):

a = 0
b = n-1
while True:
  h = (a+b)//2 ## // is the integer division, so h is an integer
  if L[h] == 0:
    return h
  elif L[h] > 0:
    b = h
  elif L[h] < 0:
    a = h

a et b sont les index entre lesquels 0 doit être trouvé. Chaque fois que nous entrons dans la boucle, nous utilisons un index entre a et b et l'utilisons pour affiner la zone à rechercher.

Dans le pire des cas, il faut attendre que a et b soient égaux. Mais combien d'opérations cela prend-il? Pas n, car chaque fois que nous entrons dans la boucle, nous divisons la distance entre a et b d'environ deux. Au contraire, la complexité est O (log n).

Explication

Note: Lorsque nous écrivons "log", nous entendons le logarithme binaire, ou log base 2 (que nous écrirons "log_2"). Comme O (log_2 n) = O (log n) (vous pouvez faire le calcul), nous utiliserons "log" au lieu de "log_2".

Appelons x le nombre d'opérations: on sait que 1 = n / (2 ^ x).

Donc 2 ^ x = n, alors x = log n

Conclusion

Face à des divisions successives (que ce soit par deux ou par un nombre quelconque), rappelez-vous que la complexité est logarithmique.

O (log n) types d'algorithmes

Disons que nous avons un problème de taille n. Maintenant, pour chaque étape de notre algorithme (que nous avons besoin d'écrire), notre problème initial devient moitié de sa taille précédente (n / 2).

Ainsi, à chaque étape, notre problème devient moitié.

Lorsque l'espace problème est réduit (c.-à-d. Complètement résolu), il ne peut plus être réduit (n devient égal à 1) après avoir quitté la condition de contrôle.

1. Disons à la kième étape ou au nombre d'opérations:

   taille du problème = 1

2. Mais nous savons à la cinquième étape, notre taille de problème devrait être:

   taille du problème = n / 2 ^k

3. Du 1 et 2:

   n / 2 ^k = 1 ou

   n = 2 ^k

4. Prenez le journal des deux côtés

   log _e n = k log _e 2

   ou

   k = log _e n / log _e 2

5. Utilisation de log log _x m / log _x n = log _n m

   k = log ₂ n

   ou simplement k = log n

Maintenant, nous savons que notre algorithme peut fonctionner au maximum jusqu'à log n, d'où la complexité du temps.
O (log n)

Un exemple très simple dans le code pour supporter le texte ci-dessus est:

for(int i=1; i<=n; i=i*2)
{
    // perform some operation
}

Alors maintenant, si quelqu'un vous demande si n est 256, combien de pas cette boucle (ou tout autre algorithme qui réduit la taille de son problème en deux) sera exécutée très facilement.

k = log ₂ 256

k = log ₂ 2 ⁸ (=> log _a a = 1)

k = 8

Un autre très bon exemple pour un cas similaire est l' algorithme de recherche binaire .

int bSearch(int arr[],int size,int item){
 int low=0;
 int high=size-1;

 while(low<=high){                 
     mid=low+(high-low)/2;                 
     if(arr[mid]==item)                        
         return mid;                 
     else if(arr[mid]<item)                         
         low=mid+1;                
     else  high=mid-1;      
     }  
  return –1;// Unsuccessful result
}