CS- Semaine 3

L'algorithme est un ensemble d'instructions données dans un ordre spécifique pour résoudre un problème. Les algorithmes diffèrent par leur vitesse et la quantité de mémoire qu'ils occupent. Dans le processus de programmation, la plupart des algorithmes sont basés sur la recherche de données (recherche) et le tri (tri). Faisons connaissance avec les algorithmes de récupération de données :

Recherche linéaire (Recherche linéaire)

Donnons-nous le tableau suivant :

[20, 500, 10, 5, 100, 1, 50]

Lors de la visualisation d'un tableau, il peut être vu comme sept armoires rouges côte à côte comme ceci :

Nous devons trouver 50 nombres dans ce tableau. L'ordinateur doit vérifier chaque casier pour trouver le numéro 50. Nous appelons ce processus, c'est-à-dire la recherche d'un nombre, d'un caractère ou d'un autre élément spécifique dans un tableau "recherche".
Nous pouvons transmettre notre tableau à un algorithme et lui demander d'ouvrir les placards et de déterminer si le nombre 50 s'y trouve. De ce fait, l’algorithme nous répondra « oui » ou « non » (vrai ou faux).

Nous pouvons construire un algorithme en utilisant les instructions suivantes :

Chapdan o‘ngga har bir eshikni tekshirish:
    Agar 50 soni bor bo‘lsa:
        Ha deb qaytaramiz (return true)
Yo‘q deb qaytaramiz (return false)

Les instructions ci-dessus sont un pseudocode lisible par l'homme et sont une représentation plus simple des commandes données à un ordinateur.

Nous pouvons implémenter l'algorithme de recherche linéaire en C en utilisant le code suivant :

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Butun sonlardan iborat massiv berilgan
    int numbers[] = {20, 500, 10, 5, 100, 1, 50};

    // Kiritilgan sonni massivdan qidiramiz
    int n = get_int("Number: ");
    for (int i = 0; i < 7; i++)
    {
        if (numbers[i] == n)
        {
            printf("Topildi\n");
            return 0;
        }
    }
    printf("Topilmadi\n");
    return 1;
}

Ici, une recherche linéaire est effectuée à l'aide d'une boucle for.
return 0 signifie que le programme s'est terminé avec succès et que le programme est quitté.
return 1 - indique qu'une erreur s'est produite dans le programme.

---

Recherche binaire

Recherche binaire est un autre algorithme utilisé pour rechercher le nombre 50.
Si les valeurs du tableau sont triées par ordre croissant, on peut donner le pseudocode de recherche binaire comme suit :

Agar tekshiriladigan element qolmagan bo‘lsa:
    Yo‘q deb qaytaramiz (return false)
Agar massivning[o‘rta elementi] 50 soniga teng bo‘lsa:
    Ha deb qaytaramiz (return true)
Agar massivning[o‘rta elementi] > 50:
    Massivning chap yarmidan qidiramiz
Agar massivning[o‘rta elementi] < 50:
    Massivning o‘ng yarmidan qidiramiz

---

Notation grand O

La Big O notation est utilisée pour analyser le temps nécessaire à l'exécution de l'algorithme. Regardons le graphique suivant :

"Taille des données d'entrée" – axe x ; "Il est temps de trouver une solution" – axe y ;
L'efficacité de l'algorithme est déterminée par la forme de sa courbe :
O(n²) est le pire temps de performance.
O(log n) est le temps d'exécution le plus rapide.

Le temps d'exécution de l'algorithme de recherche linéaire est O(n), puisque dans le pire des cas, n étapes peuvent être nécessaires.
Et le temps nécessaire pour que l'algorithme de recherche binaire fonctionne est O(log n), car dans le pire des cas, le nombre d'étapes diminue de plus en plus.

Il y a deux cas qui intéressent les programmeurs :

• Pire des cas ou limite supérieure (limite supérieure).
• Meilleur cas ou limite inférieure (limite inférieure).

Le symbole

Ω est utilisé pour désigner le meilleur des cas (borne inférieure) de l'algorithme, par exemple Ω(n).

Le symbole

TH indique le cas où les limites supérieure et inférieure sont les mêmes, c'est-à-dire que les meilleurs et les pires temps de fonctionnement sont les mêmes.

---

Algorithmes de tri (Tri)

Le tri est le processus de transformation d'une liste de valeurs non ordonnées en valeurs ordonnées.
Lorsqu'un tableau est trié, il est beaucoup plus facile pour un ordinateur d'y rechercher un élément spécifique. Par exemple, recherche binaire (recherche binaire) fonctionne sur un tableau trié mais pas sur un tableau non trié.

Il existe de nombreux types d’algorithmes de tri. Considérons l'un d'entre eux tri par sélection (tri par sélection). Donnons-nous un tableau comme celui-ci :

Le pseudocode de l'algorithme de la méthode de sélection est le suivant :

[20, 500, 10, 5, 100, 1, 50]

Analyse des étapes :

• Parcourir les éléments du tableau pour la première fois prend n à 1 étapes.
• La deuxième fois n - 2 étapes sont nécessaires.
• Poursuivant cette logique, les étapes requises peuvent s'exprimer comme suit :

Chapdan o‘ngga har bir eshikni tekshirish:
    Agar 50 soni bor bo‘lsa:
        Ha deb qaytaramiz (return true)
Yo‘q deb qaytaramiz (return false)

En simplifiant cette formule, on obtient : n(n-1)/2 ou O(n²).
Ainsi, l'algorithme de la méthode de sélection trie dans l'ordre O(n²) dans le pire des cas. Même si toutes les valeurs sont triées, le nombre d'étapes ne change pas, donc le meilleur des cas est dans l'ordre O(n²).

---

Algorithme de tri à bulles (Tri à bulles)

Tri à bulles est un autre algorithme de tri dans lequel nous "promouvons" des valeurs plus grandes en permutant les éléments à plusieurs reprises.

Le pseudocode de l'algorithme de tri à bulles est le suivant :

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Butun sonlardan iborat massiv berilgan
    int numbers[] = {20, 500, 10, 5, 100, 1, 50};

    // Kiritilgan sonni massivdan qidiramiz
    int n = get_int("Number: ");
    for (int i = 0; i < 7; i++)
    {
        if (numbers[i] == n)
        {
            printf("Topildi\n");
            return 0;
        }
    }
    printf("Topilmadi\n");
    return 1;
}

Au fur et à mesure que nous trions le tableau, nous savons qu'une plus grande partie sera triée, il nous suffit donc de vérifier les paires qui ne sont pas encore triées.
Par conséquent, l'algorithme de tri à bulles fonctionne dans le pire des cas O(n²) si le tableau n'est pas trié, et dans le meilleur des cas O(n) si le tableau est déjà trié.

Nous pouvons voir visuellement comment fonctionnent les algorithmes de tri dans cette page.

Cet article utilise la source CS50x 2024.

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!