演算法是一組以特定順序給出的用於解決問題的指令。演算法的速度和占用記憶體量有所不同。在程式設計過程中，大多數演算法都是基於資料搜尋（搜尋）和排序（排序）。讓我們來熟悉一下資料檢索演算法：
讓我們得到以下數組：
[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 符號用於分析運行演算法所需的時間。我們來看下圖：
「輸入資料大小」 – x 軸； 「求解時間」 – y 軸；
演算法的效率由其曲線的形狀決定：
O(n²) 是最差性能時間。
O(log n) 是最快的執行時間。
線性搜尋演算法的運行時間是 O(n)，因為在最壞的情況下可能需要 n 步。
而二分查找演算法工作的時間是O(log n)，因為在最壞的情況下，步數會越來越少。
程式設計師感興趣的有兩種情況：
Ω 用來表示演算法的最佳情況 （下界），例如 Ω(n)。
符號TH表示上下界相同的情況，即最好和最差運行時間相同。
排序是將無序值清單變更為有序值的過程。
當陣列排序後，電腦可以更輕鬆地搜尋其中的特定元素。例如，二分搜尋 （二分搜尋） 適用於已排序的數組，但不適用於未排序的數組。
排序演算法有很多種。讓我們考慮其中一個選擇排序 （選擇排序）。讓我們得到一個像這樣的陣列：
選擇方法演算法的偽代碼如下：
[20, 500, 10, 5, 100, 1, 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)
簡化這個公式，我們得到：n(n-1)/2 或 O(n²)。
因此，選擇方法的演算法在最壞情況下按 O(n²) 順序排序。即使所有值都已排序，步數也不會改變，因此最好的情況是 O(n²) 順序。
冒泡排序是另一種排序演算法，我們透過重複排列元素來「提升」更大的值。
冒泡排序演算法的偽代碼如下：
#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中文網其他相關文章！
