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中文网其他相关文章！