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 



<p>这里使用 for 循环执行线性搜索。<br>
return 0 表示程序成功结束，程序退出。<br>
return 1 - 表示程序中发生错误。</p>

<hr>
<h2>
  
  
  二分查找
</h2>

<p><em>二分查找</em>是另一种用于搜索数字 50 的算法。<br>
如果数组中的值按升序排序，我们可以给出二分查找的伪代码如下：<br>
</p>

<pre class="brush:php;toolbar:false">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] 




<hr>

<h2>
  
  
  大O表示法
</h2>

<p><strong>大O</strong> <strong>符号</strong>用于分析运行算法所需的时间。我们来看下图：</p>

<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173590294458453.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="CS- Week 3"></p>

<p><em>“输入数据大小”</em> – x 轴； <em>“求解时间”</em> – y 轴；<br>
算法的效率由其曲线的形状决定：<br>
O(n²) 是最差性能时间。<br>
O(log n) 是最快的执行时间。</p><p>线性搜索算法的运行时间是 O(n)，因为在最坏的情况下可能需要 n 步。<br>
而二分查找算法工作的时间是O(log n)，因为在最坏的情况下，步数会越来越少。</p>

<p>程序员感兴趣的有两种情况：</p>

• 最坏情况或上限（上限）。
• 最佳情况或下限（下限）。

符号

Ω 用于表示算法的最佳情况 （下界），例如 Ω(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 



<p>当我们对数组进行排序时，我们知道更多的数组将被排序，因此我们只需要检查尚未排序的对。<br>
因此，如果数组未排序，冒泡排序算法在最坏的情况下工作 O(n²)，如果数组已排序，则在最好的情况下工作 O(n)。</p>
<p>我们可以在此页面直观地看到排序算法是如何工作的。</p>

<blockquote>
<p>本文使用 CS50x 2024 源码。</p>
</blockquote>


          

            
        </stdio.h></cs50.h>

以上是CS-第 3 周的详细内容。更多信息请关注PHP中文网其他相关文章！