CS-第 3 周

wufei123 2025-01-05 阅读:6 评论:0
算法是解决问题的指令集,其执行速度和内存占用各不相同。编程中,许多算法都基于数据搜索和排序。本文将介绍几种数据检索和排序算法。 线性搜索 假设有一个数组 [20, 500, 10, 5, 100, 1, 50],需要查找数字 50。线性搜索...

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

线性搜索

假设有一个数组 [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
");
            return 0;
        }
    }
    printf("false
");
    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 周的详细内容,更多请关注知识资源分享宝库其它相关文章!

版权声明

本站内容来源于互联网搬运,
仅限用于小范围内传播学习,请在下载后24小时内删除,
如果有侵权内容、不妥之处,请第一时间联系我们删除。敬请谅解!
E-mail:dpw1001@163.com

分享:

扫一扫在手机阅读、分享本文

发表评论
热门文章
  • 华为 Mate 70 性能重回第一梯队 iPhone 16 最后一块遮羞布被掀

    华为 Mate 70 性能重回第一梯队 iPhone 16 最后一块遮羞布被掀
    华为 mate 70 或将首发麒麟新款处理器,并将此前有博主爆料其性能跑分将突破110万,这意味着 mate 70 性能将重新夺回第一梯队。也因此,苹果 iphone 16 唯一能有一战之力的性能,也要被 mate 70 拉近不少了。 据悉,华为 Mate 70 性能会大幅提升,并且销量相比 Mate 60 预计增长40% - 50%,且备货充足。如果 iPhone 16 发售日期与 Mate 70 重合,销量很可能被瞬间抢购。 不过,iPhone 16 还有一个阵地暂时难...
  • 惠普新款战 99 笔记本 5 月 20 日开售:酷睿 Ultra / 锐龙 8040,4999 元起

    惠普新款战 99 笔记本 5 月 20 日开售:酷睿 Ultra / 锐龙 8040,4999 元起
    本站 5 月 14 日消息,继上线官网后,新款惠普战 99 商用笔记本现已上架,搭载酷睿 ultra / 锐龙 8040处理器,最高可选英伟达rtx 3000 ada 独立显卡,售价 4999 元起。 战 99 锐龙版 R7-8845HS / 16GB / 1TB:4999 元 R7-8845HS / 32GB / 1TB:5299 元 R7-8845HS / RTX 4050 / 32GB / 1TB:7299 元 R7 Pro-8845HS / RTX 2000 Ada...
  • 酷凛 ID-COOLING 推出霜界 240/360 一体水冷散热器,239/279 元

    酷凛 ID-COOLING 推出霜界 240/360 一体水冷散热器,239/279 元
    本站 5 月 16 日消息,酷凛 id-cooling 近日推出霜界 240/360 一体式水冷散热器,采用黑色无光低调设计,分别定价 239/279 元。 本站整理霜界 240/360 散热器规格如下: 酷凛宣称这两款水冷散热器搭载“自研新 V7 水泵”,采用三相六极马达和改进的铜底方案,缩短了水流路径,相较上代水泵进一步提升解热能力。 霜界 240/360 散热器的水泵为定速 2800 RPM 设计,噪声 28db (A)。 两款一体式水冷散热器采用 27mm 厚冷排,...
  • Nginx服务器的HTTP/2协议支持和性能提升技巧介绍

    Nginx服务器的HTTP/2协议支持和性能提升技巧介绍
    Nginx服务器的HTTP/2协议支持和性能提升技巧介绍 引言:随着互联网的快速发展,人们对网站速度的要求越来越高。为了提供更快的网站响应速度和更好的用户体验,Nginx服务器的HTTP/2协议支持和性能提升技巧变得至关重要。本文将介绍如何配置Nginx服务器以支持HTTP/2协议,并提供一些性能提升的技巧。 一、HTTP/2协议简介:HTTP/2协议是HTTP协议的下一代标准,它在传输层使用二进制格式进行数据传输,相比之前的HTTP1.x协议,HTTP/2协议具有更低的延...
  • 两个表格切换的快捷键是什么

    两个表格切换的快捷键是什么
    两个表格切换的快捷键是“ctrl+pageup”和“ctrl+pagedown”,按键盘上的“ctrl+pageup”键是向右切换表格,按“ctrl+pagedown”键是向左切换表格。 本教程操作环境:windows7系统、Microsoft Office Excel2010版、Dell G3电脑。 两个工作表之间切换是Ctrl+Tab,两个工作簿之间切换是Ctrl+PageUP和Ctrl+PageDown。 打开Excel表格,打开几个工作簿。 按键盘上的Ctrl+P...