CS-第 3 週

演算法是一組以特定順序給出的用於解決問題的指令。演算法的速度和占用記憶體量有所不同。在程式設計過程中，大多數演算法都是基於資料搜尋（搜尋）和排序（排序）。讓我們來熟悉一下資料檢索演算法：

線性搜尋（線性搜尋）

讓我們得到以下數組：

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

當視覺化一個陣列時，它可以被視為七個並排的紅色櫃子，如下所示：

我們要從這個陣列中找出 50 個數字。計算機必須檢查每個儲物櫃才能找到數字 50。我們稱這個過程為在陣列中搜尋特定的數字、字元或其他元素「搜尋」.
我們可以將陣列傳遞給演算法，並要求演算法打開櫥櫃並確定數字 50 是否存在。結果，演算法將回答我們「是」或「否」（正確或錯誤）。

我們可以使用以下指令來建構演算法：

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

上面的說明是人類可讀的偽代碼，是向電腦發出的命令的更簡單表示。

我們可以使用以下程式碼在 C 中實作線性搜尋演算法：

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

這裡使用 for 迴圈執行線性搜尋。
return 0 表示程式成功結束，程式退出。
return 1 - 表示程式中發生錯誤。

---

二分查找

二分查找是另一個用來搜尋數字 50 的演算法。
如果數組中的值按升序排序，我們可以給出二分查找的偽代碼如下：

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

---

大O表示法

大O 符號用於分析運行演算法所需的時間。我們來看下圖：

「輸入資料大小」 – x 軸； 「求解時間」 – y 軸；
演算法的效率由其曲線的形狀決定：
O(n²) 是最差性能時間。
O(log n) 是最快的執行時間。

線性搜尋演算法的運行時間是 O(n)，因為在最壞的情況下可能需要 n 步。
而二分查找演算法工作的時間是O(log n)，因為在最壞的情況下，步數會越來越少。

程式設計師感興趣的有兩種情況：

• 最壞情況或上限（上限）。
• 最佳情況或下限（下限）。

符號

Ω 用來表示演算法的最佳情況 （下界），例如 Ω(n)。

符號

TH表示上下界相同的情況，即最好和最差運行時間相同。

---

排序演算法（Sorting）

排序是將無序值清單變更為有序值的過程。
當陣列排序後，電腦可以更輕鬆地搜尋其中的特定元素。例如，二分搜尋 （二分搜尋） 適用於已排序的數組，但不適用於未排序的數組。

排序演算法有很多種。讓我們考慮其中一個選擇排序 （選擇排序）。讓我們得到一個像這樣的陣列：

選擇方法演算法的偽代碼如下：

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

步驟分析：

• 第一次遍歷陣列元素需要 n - 1 步。
• 第二次需要n - 2步。
• 繼續這個邏輯，所需的步驟可以表示為：

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

簡化這個公式，我們得到：n(n-1)/2 或 O(n²)。
因此，選擇方法的演算法在最壞情況下按 O(n²) 順序排序。即使所有值都已排序，步數也不會改變，因此最好的情況是 O(n²) 順序。

---

冒泡排序演算法（Bubble sort）

冒泡排序是另一種排序演算法，我們透過重複排列元素來「提升」更大的值。

冒泡排序演算法的偽代碼如下：

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

當我們對數組進行排序時，我們知道更多的數組將被排序，因此我們只需要檢查尚未排序的對。
因此，如果數組未排序，冒泡排序演算法在最壞的情況下工作 O(n²)，如果數組已排序，則在最好的情況下工作 O(n)。

我們可以在此頁面直觀地看到排序演算法是如何運作的。

本文使用 CS50x 2024 原始碼。

以上是CS-第 3 週的詳細內容。更多資訊請關注PHP中文網其他相關文章！