Complexité de temps de recherche linéaire

La recherche linéaire est une recherche séquentielle. Cette méthode de recherche vérifie les éléments de la liste un par un, à partir du premier élément. Quand il voit la première occurrence de l'élément qu'il recherche, la recherche s'arrête. L'élément qu'il recherche est appelé la cible. Si l'élément n'est pas trouvé, tous les éléments de la liste sont vérifiés. La recherche linéaire est un algorithme de recherche très simple que chaque programmeur doit apprendre, officiellement ou intuitivement.

Considérez la liste suivante:

I j a c b g d h e f

Pour rechercher un, le programme doit itérer la liste 3 fois. Pour rechercher G, le programme doit itérer la liste 6 fois. Pour rechercher F, le programme doit itérer la liste 10 fois. Pour rechercher K ou toute lettre qui n'est pas dans la liste, le programme doit itérer la liste 10 fois et ne trouvera pas de match.

Le but de cet article est de produire la complexité du temps pour la recherche linéaire. La programmation se fait dans la discussion C suivante.

Algorithme de recherche linéaire

L'algorithme pour la recherche linéaire est simple. Supposons que la liste est un tableau basé sur les zéro. Laissez la variable qui représente chaque index être i. Laissez le tableau avoir le nom un. Les étapes sont les suivantes:

• • Que je sois 0.
  • Si un [i] est la cible, la valeur pour i est renvoyée et que la recherche se termine avec succès.
  • Si un [i] n'est pas la cible, augmentez I par 1 et répétez l'étape précédente.
  • Alors que I est inférieur à N, où N est la longueur du tableau, continuez à répéter les deux étapes précédentes dans l'ordre.
  • Continuez de cette façon jusqu'à ce que la cible soit trouvée ou non trouvée.

La recherche se termine avec succès lorsque la cible est trouvée. La recherche se termine sans succès lorsque la cible n'est pas trouvée. Pour une fin infructueuse, tous les n éléments sont vérifiés.

Complexité temporelle

La complexité du temps est le nombre d'opérations principales pour un code pour terminer sa tâche. Vérifier si la cible correspond à un élément est une opération. Il y a la complexité temporelle pire des cas, la complexité du temps moyen et la complexité du meilleur cas.

Complexité du temps pire des cas

Le nombre maximal d'opérations se produit lorsque la cible est à la fin de la liste ou n'est pas du tout dans la liste. C'est le pire cas. La complexité du temps pire des cas est donnée comme suit:

Sur)

Cela utilise la notation Big-O. La notation Big-O commence par la majuscule O, suivie de parenthèses. À l'intérieur des parenthèses se trouve l'expression du nombre d'opérations pour résoudre la tâche.

Complexité du temps de la meilleure case

Si le premier élément de la liste est la cible, une seule opération de vérification est nécessaire pour la recherche. C'est-à-dire qu'une seule opération est nécessaire pour la recherche. C'est la complexité du temps de la meilleure case. Il est écrit comme:

O (1)

Où 1 entre parenthèses signifie une opération.

Complexité du temps de cas moyen

La complexité du temps de cas moyen dépend de la distribution de probabilité. Si chaque élément peut être en position, alors chaque élément est également susceptible d'être recherché. Dans cette situation, la complexité du temps de cas moyen est donnée comme suit:

O (n / 2)

Programmation en c

La recherche linéaire est probablement la recherche la plus simple pour rédiger un programme pour. Suivez simplement l'algorithme, qui est répété ici, pour référence facile:

• • Que je sois 0.
  • Si un [i] est la cible, la valeur pour i est renvoyée et que la recherche se termine avec succès.
  • Si un [i] n'est pas la cible, augmentez I par 1 et répétez l'étape précédente.
  • Alors que I est inférieur à N, où N est la longueur du tableau, continuez à répéter les deux étapes précédentes dans l'ordre.
  • Continuez de cette façon jusqu'à ce que la cible soit trouvée ou non trouvée.

Essentiellement, le programme est le suivant:

#inclure
int linearsearch (char a [], int n, char t)
pour (int i = 0; iif (t == a [i])
retour i;

Il commence par inclure le stdio.H Bibliothèque H qui est responsable de l'entrée et de la sortie. Après cela, il y a la définition de la fonction linearsearch (). Le code principal de la définition de la fonction est la boucle. La boucle à forte échec scanne le tableau du début à la fin, à la recherche d'un match de la cible. Si une cible est trouvée, l'index de l'élément correspondant dans le tableau est renvoyé. Afin d'obtenir le numéro ordinal de l'indice de l'élément correspondant, ajoutez 1 à l'indice basé sur zéro.

Une fonction principale C appropriée pour le programme ci-dessus est la suivante:

int main (int argc, char ** argv)

int n = 10;
char a [] = 'i', 'j', 'a', 'c', 'b', 'g', 'd', 'h', 'e', ​​'f';
int ret = linearSearch (a, n, 'g');
printf ("% i \ n", ret);
retour 0;

La première déclaration de la fonction principale C déclare le nombre d'éléments dans le tableau donné. Après cela, il y a le tableau avec le nom A. Il y a dix personnages dans le tableau. La déclaration du tableau commence par «char» et non «int». À partir de là, la fonction LinearSearch () définie est appelée. Le premier argument à l'appel de fonction est le tableau. Le deuxième argument est le nombre d'éléments dans le tableau. Le troisième argument est la cible qui est la lettre dont la présence dans le tableau est vérifiée. S'il est présent, l'indice basé sur zéro est renvoyé. S'il n'est pas présent, rien n'est retourné.

L'instruction suivante imprime tout index renvoyé. Pour cette fonction principale C, 5 est imprimé. Si 1 est ajouté à 5, ce serait 6, ce qui est l'indice ordinal.

Conclusion

La complexité du temps pire des cas est donnée comme suit:

Sur)

Cela utilise la notation Big-O. La notation Big-O commence par la majuscule O, suivie de parenthèses. À l'intérieur des parenthèses se trouve l'expression du nombre d'opérations pour résoudre la tâche.

Si le premier élément de la liste est la cible, une seule opération de vérification est nécessaire pour la recherche. C'est-à-dire qu'une seule opération est nécessaire pour la recherche. C'est la complexité du temps de la meilleure case. Il est écrit comme:

O (1)

Où 1 entre parenthèses signifie une opération.

La complexité du temps de cas moyen dépend de la distribution de probabilité. Si chaque élément peut être dans n'importe quelle position, chaque élément est également susceptible d'être recherché par cet algorithme. Dans cette situation, la complexité du temps de cas moyen est:

O (n / 2)