『初阶数据结构 • C语言』③ - 算法分析专业工具——大O记法

这篇具有很好参考价值的文章主要介绍了『初阶数据结构 • C语言』③ - 算法分析专业工具——大O记法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

大o记法,排序算法(C语言版),新星计划免费学习专栏·数据结构与算法,算法,数据结构,c语言

本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余,我决定把这本书精彩的部分摘录出来与大家分享。  


大o记法,排序算法(C语言版),新星计划免费学习专栏·数据结构与算法,算法,数据结构,c语言 

 文章来源地址https://www.toymoban.com/news/detail-596601.html

写在前面

从之前的章节中我们了解到,影响算法性能的主要因素是其所需的步数。

然而,我们不能简单地把一个算法记为“22步算法”,把另一个算法记为“400步算法”,因为一个算法的步数并不是固定的。

以线性查找为例,它的步数等于数组的元素数量。如果数组有22个元素,线性查找就需要 22步;如果数组有 400个元素,线性查找就需要 400步。

量化线性查找效率的更准确的方式应该是:对于具有 N 个元素的数组,线性查找最多需要 N步

为了方便表达数据结构和算法的时间复杂度,计算机科学家从数学界借鉴了一种简洁又通用的方式,那就是大 O 记法。

掌握了大 O记法,就掌握了算法分析的专业工具。


1.大O:数步数

为了统一描述,大 O不关注算法所用的时间,只关注其所用的步数。

第 1章介绍过,数组不论多大,读取都只需 1步。用大 O记法来表示,就是:O(1)

O(1)意味着一种算法无论面对多大的数据量,其步数总是相同的。

就像无论数组有多大,读取元素都只要 1 步。这 1 步在旧机器上也许要花 20 分钟,而用现代的硬件却只要 1 纳秒。但这两种情况下,读取数组都是 1步。其他也属于 O(1)的操作还包括数组末尾的插入与删除。之前已证明,无论数组有多大,这两种操作都只需 1步,所以它们的效率都是O(1)。

下面研究一下大 O 记法如何描述线性查找的效率。回想一下,线性查找在数组上要逐个检查每个格子。在最坏情况下,线性查找所需的步数等于格子数。即如前所述:对于 N个元素的数组,线性查找需要花 N步。

用大 O记法来表示,即为:O(N)


2.常数时间与线性时间

从 O(N)可以看出,大 O 记法不只是用固定的数字(如 22、440)来表示算法的步数,而是基于要处理的数据量来描述算法所需的步数。

或者说,大 O 解答的是这样的问题:当数据增长时,步数如何变化

O(N)算法所需的步数等于数据量,意思是当数组增加一个元素时,O(N)算法就要增加 1步。而 O(1)算法无论面对多大的数组,其步数都不变

大o记法,排序算法(C语言版),新星计划免费学习专栏·数据结构与算法,算法,数据结构,c语言

当数据增加一个单位时,算法也随之增加一步。也就是说,数据越多,算法所需的步数就越多。O(N)也被称为线性时间

相比之下,O(1)则为一条水平线,因为不管数据量是多少,算法的步数都恒定。所以,O(1)也被称为为常数时间

因为大 O主要关注的是数据量变动时算法的性能变化,所以,即使一个算法的恒定步数不是 1,它也可以被归类为 O(1)。

大o记法,排序算法(C语言版),新星计划免费学习专栏·数据结构与算法,算法,数据结构,c语言

O(1)永远比O(N)更高效,原因在于,当元素数量无限增多时,O(N)总会在某一临界值超过O(1)


3.同一算法,不同场景

之前的章节我们提到,线性查找并不总是 O(N)的。当要找的元素在数组末尾,那确实是 O(N)。但如果它在数组开头,1步就能找到的话,那么技术上来说应该是 O(1)。所以概括来说,线性查找的最好情况是 O(1),最坏情况是 O(N)。

虽然大 O 可以用来表示给定算法的最好和最坏的情景,但若无特别说明,大 O 记法一般都是指最坏情况

这种悲观主义其实是很有用的:知道各种算法会差到什么程度,能使我们做好最坏打算,以选出最适合的算法。


4.第三种算法

上一章我们学到:在同一个有序数组里,二分查找比线性查找要快。

算法为何重要(二分查找)http://t.csdn.cn/YPs4s下面就来看看如何用大O记法描述二分查找。

二分查找的大 O记法是:O(log N)

简单分析一下,倘若要用二分查找在含有N个元素的有序数组中查找某个元素。

二分查找的基本思想是,每次我们都能排除掉一半的数据。

所以考虑最坏情况,就是数组里没有我们要查找的元素,那么我们每次排除一半的元素,多

少次才能全部排除(或者说只剩一个元素)呢?

答案是  。

简单来说,O(log N)意味着该算法当数据量翻倍时,步数加 1

这里我们所提过的 3种时间复杂度,按照效率由高到低来排序的话,会是这样:

O(1)<O(log N)<O(N)

大o记法,排序算法(C语言版),新星计划免费学习专栏·数据结构与算法,算法,数据结构,c语言

现在回到大 O记法。当我们说 O(log N)时,其实指的是 O(log 2 N),不过为了方便就省略了2而已。简单来说,O(log N)算法的步数等于二分数据直至元素剩余 1 个的次数。

下表是 O(N)和 O(log N)的效率对比。

大o记法,排序算法(C语言版),新星计划免费学习专栏·数据结构与算法,算法,数据结构,c语言

每次数据量翻倍时,O(N)算法的步数也跟着翻倍,O(log N)算法却只需加 1。

总结

学会大 O记法,我们在比较算法时就有了一致的参考系。有了它,我们就可以在现实场景中测量各种数据结构和算法,写出更快的代码,更轻松地应对高负荷的环境。 

下一章会用一个实际的例子,让你看到大 O记法如何帮助我们显著地提高代码的性能。

大o记法,排序算法(C语言版),新星计划免费学习专栏·数据结构与算法,算法,数据结构,c语言

 

到了这里,关于『初阶数据结构 • C语言』③ - 算法分析专业工具——大O记法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构和算法初阶(C语言)】复杂链表(随机指针,随机链表的复制)题目详解+链表顺序表结尾

    目录  1.随机链表的复制 1.2题目描述  1.3题目分析 1.4解题: 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语 一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random   该指针可以指向链表中的任何节点或空节点。        构造这个链表的  深拷贝 。 深拷贝

    2024年03月10日
    浏览(87)
  • 『初阶数据结构 • C语言』① - 数据结构为何重要

    本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余,我决定把这本书精彩的部分摘录出来与大家分享。 数组是计算机科学中最基本的数据结构之一。如果你用过数组,那么应该知道它就是一个含有 数据的列表。它有多种用途,适用于各种场景,下面

    2024年02月16日
    浏览(47)
  • go专业数据结构与算法

    2.数组概念 3.golang实现数组结构 4.golang实现数组迭代器 5.数组栈的高级实现 6.栈模拟低级递归 7.斐波那契数列栈模拟递归 8.递归实现文件夹遍历 9.栈模拟文件递归 10.层级展示文件夹 11.数组队列的实现 12.队列实现遍历文件夹 13.循环队列 14.链式栈 15.链式队列 16.作业 17.为什么需

    2024年02月13日
    浏览(50)
  • C语言完整版笔记(初阶,进阶,深刨,初阶数据结构)

    1.初阶: 1.1C语言初阶易忘知识点速记 2.进阶:  1.2C语言进阶易忘点速记 3.深剖: 2.1C语言重点解剖要点速记 2.2C语言重点解剖操作符要点速记   2.3C语言重点解剖预处理要点速记 2.4C语言重点解剖指针和数组要点速记 2.5C语言重点解剖内存管理函数要点速记 4.数据结构:

    2024年02月16日
    浏览(38)
  • 数据结构初阶(用C语言实现简单数据结构)--栈和队列

    ✨✨欢迎来到T_X_Parallel的博客!!       🛰️博客主页:T_X_Parallel       🛰️专栏 : 数据结构初阶       🛰️欢迎关注:👍点赞🙌收藏✍️留言 这小猫真好看 言归正传,通过上篇有关顺序表和链表的博客,可以了解到线性表的一些大致特征,这篇博

    2024年02月08日
    浏览(41)
  • 【数据结构初阶】之堆(C语言实现)

    前言 :在二叉树基础篇我们提到了二叉树的顺序实现,今天让我们来学习一下特殊的二叉树———堆的相关知识。 📃 博客主页: 小镇敲码人 💞 热门专栏:数据结构与算法 🚀 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌏 任尔江湖满血骨,我自踏雪寻梅香。 万千浮云遮碧月

    2024年04月09日
    浏览(81)
  • 『初阶数据结构 • C语言』⑤ - 选择排序

    本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余,我决定把这本书精彩的部分摘录出来与大家分享。     目录 写在前面 1.选择排序 2.选择排序实战 3.选择排序的实现 4.选择排序的效率 5.忽略常数 6.大O的作用 7.总结     大 O 是一种能够比较算法效

    2024年02月14日
    浏览(44)
  • 『初阶数据结构 • C语言』④ - 冒泡排序

      本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余,我决定把这本书精彩的部分摘录出来与大家分享。      本章内容 写在前面 1.冒泡排序 2.冒泡排序实战 3.冒泡排序的实现 4.冒泡排序的效率 5.二次问题 6.线性解决 7.总结     大 O记法能客观地衡量

    2024年02月16日
    浏览(45)
  • 『初阶数据结构 • C语言』⑥ - 插入排序&希尔排序

    学习目标 写在前面 1.插入排序 2.插入排序实战  3.插入排序的实现  4.插入排序的效率 5.平均情况 6.希尔排序 7.希尔排序的实现 8.希尔排序的效率 9.总结   之前我们衡量一个算法的效率时,都是着眼于它在最坏情况下需要多少步。原因很简单,连最坏的情况都做足准备了,其

    2024年02月15日
    浏览(42)
  • 数据结构初阶之顺序表(C语言实现)

    顺序表是数据结构里面很基础的一类,它是线性表的一种,其它线性表还有链表、栈和队列等,今天来和博主一起学习关于顺序表的知识吧。 顺序表,它分为两类: 动态顺序表 和 静态顺序表 ,这两个表的区别就是 前者的空间不固定 ,是 支持扩容 的,后者的 空间是固定

    2024年02月03日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包