CS-第 3 周-C++-PHP中文网

CS-第 3 周

碧海醫心

发布： 2024-12-26 12:21:01

转载

414人浏览过

算法是解决问题的指令集，其执行速度和内存占用各不相同。编程中，许多算法都基于数据搜索和排序。本文将介绍几种数据检索和排序算法。

线性搜索

假设有一个数组 [20, 500, 10, 5, 100, 1, 50]，需要查找数字 50。线性搜索算法会逐个检查数组中的每个元素，直到找到目标值或遍历完整个数组。

CS-第 3 周

算法流程图如下：

CS-第 3 周

线性搜索的伪代码如下：

检查每个元素：
    如果找到目标值：
        返回 true
返回 false

登录后复制

C语言实现：

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    int numbers[] = {20, 500, 10, 5, 100, 1, 50};
    int n = get_int("number: ");
    for (int i = 0; i < 7; i++)
    {
        if (numbers[i] == n)
        {
            printf("true\n");
            return 0;
        }
    }
    printf("false\n");
    return 0;
}

登录后复制

线性搜索的时间复杂度为 O(n)。

二分查找

二分查找算法适用于已排序的数组。它通过不断缩小搜索范围来提高效率。

二分查找的伪代码如下：

如果数组为空：
    返回 false
如果中间元素等于目标值：
    返回 true
如果中间元素大于目标值：
    在左半部分继续查找
否则：
    在右半部分继续查找

登录后复制

二分查找的时间复杂度为 O(log n)。

大O表示法

大O表示法用于描述算法的时间复杂度。下图展示了不同时间复杂度的曲线：

CS-第 3 周

x轴表示输入数据量，y轴表示求解时间。O(log n) 表示最优时间复杂度，O(n²) 表示最差时间复杂度。

排序算法

排序算法用于将无序数据转换为有序数据。已排序的数据可以提高搜索效率，例如二分查找。

选择排序

选择排序算法的伪代码如下：

对于每个元素：
    找到剩余元素中的最小值
    将最小值与当前元素交换

登录后复制

选择排序的时间复杂度为 O(n²)，无论数据是否已排序。

CS-第 3 周

冒泡排序

冒泡排序算法通过重复比较和交换相邻元素来排序数据。

冒泡排序算法的伪代码如下：

重复 n-1 次：
    对于每个元素：
        如果相邻元素顺序错误：
            交换它们
    如果未进行任何交换：
        结束排序

登录后复制

冒泡排序的时间复杂度在最坏情况下为 O(n²)，在最好情况下为 O(n)。

本文基于cs50x 2024源码。

以上就是CS-第 3 周的详细内容，更多请关注php中文网其它相关文章！