CS – Woche 3

Algorithmus ist eine Reihe von Anweisungen, die in einer bestimmten Reihenfolge gegeben werden, um ein Problem zu lösen. Algorithmen unterscheiden sich in der Geschwindigkeit und der Menge an Speicher, die sie belegen. Im Programmierprozess basieren die meisten Algorithmen auf der Datensuche (Suche) und der Sortierung (Sortierung). Machen wir uns mit den Datenabrufalgorithmen vertraut:

Lineare Suche (Lineare Suche)

Lassen Sie uns das folgende Array erhalten:

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

Bei der Visualisierung eines Arrays kann man es als sieben rote Schränke nebeneinander sehen, etwa so:

Wir müssen 50 Zahlen aus diesem Array finden. Der Computer muss jedes Schließfach überprüfen, um die Nummer 50 zu finden. Wir nennen diesen Vorgang, also die Suche nach einer bestimmten Zahl, einem bestimmten Zeichen oder einem anderen Element in einem Array „Suche“.
Wir können unser Array an einen Algorithmus übergeben und den Algorithmus bitten, die Schränke zu öffnen und festzustellen, ob die Zahl 50 dort ist. Als Ergebnis antwortet uns der Algorithmus mit „Ja“ oder „Nein“ (wahr oder falsch).

Wir können einen Algorithmus mithilfe der folgenden Anweisungen erstellen:

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

Die obigen Anweisungen sind menschenlesbarer Pseudocode und stellen eine einfachere Darstellung der Befehle dar, die einem Computer gegeben werden.

Wir können den linearen Suchalgorithmus in C mit dem folgenden Code implementieren:

#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;
}

Hier wird eine lineare Suche mithilfe einer for-Schleife durchgeführt.
Rückgabe 0 bedeutet, dass das Programm erfolgreich beendet wurde und das Programm beendet wird.
return 1 – zeigt an, dass im Programm ein Fehler aufgetreten ist.

---

Binäre Suche

Binäre Suche ist ein weiterer Algorithmus, der zur Suche nach der Zahl 50 verwendet wird.
Wenn die Werte im Array in aufsteigender Reihenfolge sortiert sind, können wir den Pseudocode der binären Suche wie folgt angeben:

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

---

Big-O-Notation

Die Big O Notation wird verwendet, um die Zeit zu analysieren, die zum Ausführen des Algorithmus benötigt wird. Schauen wir uns die folgende Grafik an:

"Eingabedatengröße" – x-Achse; "Zeit für Lösung" – y-Achse;
Die Effizienz des Algorithmus wird durch die Form seiner Kurve bestimmt:
O(n²) ist die schlechteste Leistungszeit.
O(log n) ist die schnellste Ausführungszeit.

Die Laufzeit des linearen Suchalgorithmus beträgt O(n), da im schlimmsten Fall n Schritte erforderlich sein können.
Und die Zeit, die der binäre Suchalgorithmus benötigt, um zu funktionieren, beträgt O(log n), denn im schlimmsten Fall nimmt die Anzahl der Schritte immer mehr ab.

Es gibt zwei Fälle, die für Programmierer von Interesse sind:

• Worst Case oder Obergrenze (Obergrenze).
• Bester Fall oder Untergrenze (Untergrenze).

Das Symbol

Ω wird verwendet, um den besten Fall (Untergrenze) des Algorithmus zu bezeichnen, zum Beispiel Ω(n).

Das Symbol

TH gibt den Fall an, in dem die Ober- und Untergrenze gleich sind, d. h. die besten und schlechtesten Laufzeiten sind gleich.

---

Sortieralgorithmen (Sortierung)

Sortieren ist der Prozess der Umwandlung einer ungeordneten Liste von Werten in geordnete.
Wenn ein Array sortiert ist, ist es für einen Computer viel einfacher, darin nach einem bestimmten Element zu suchen. Beispielsweise funktioniert binäre Suche (binäre Suche) auf einem sortierten Array, aber nicht auf einem unsortierten Array.

Es gibt viele Arten von Sortieralgorithmen. Betrachten wir eine davon Auswahlsortierung (Auswahlsortierung). Lassen Sie uns ein Array wie dieses erhalten:

Der Pseudocode des Auswahlmethodenalgorithmus lautet wie folgt:

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

Schrittanalyse:

• Das erste Durchlaufen von Array-Elementen dauert n - 1 Schritte.
• Beim zweiten Mal sind n - 2 Schritte erforderlich.
• In Fortführung dieser Logik können die erforderlichen Schritte wie folgt ausgedrückt werden:

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

Wenn wir diese Formel vereinfachen, erhalten wir: n(n-1)/2 oder O(n²).
Im schlimmsten Fall sortiert der Algorithmus der Auswahlmethode also in der Reihenfolge O(n²). Selbst wenn alle Werte sortiert sind, ändert sich die Anzahl der Schritte nicht, sodass im besten Fall die Reihenfolge O(n²) vorliegt.

---

Blasensortierungsalgorithmus (Blasensortierung)

Bubble Sort ist ein weiterer Sortieralgorithmus, bei dem wir größere Werte durch wiederholtes Permutieren von Elementen „fördern“.

Der Pseudocode des Blasensortierungsalgorithmus lautet wie folgt:

#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;
}

Wenn wir das Array sortieren, wissen wir, dass mehr davon sortiert wird, daher müssen wir nur die Paare überprüfen, die noch nicht sortiert sind.
Daher funktioniert der Blasensortierungsalgorithmus im schlimmsten Fall O(n²), wenn das Array nicht sortiert ist, und im besten Fall O(n), wenn das Array bereits sortiert ist.

Auf dieser Seite können wir visuell sehen, wie die Sortieralgorithmen funktionieren.

Dieser Artikel verwendet die CS50x 2024-Quelle.

Das obige ist der detaillierte Inhalt vonCS – Woche 3. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!