数据结构与算法读书笔记(一)


什么是数据结构?什么是算法?

1. 入门:

从广义上讲:

  • 数据结构:指一组数据的存储结构

图书馆储藏书籍你肯定见过吧?为了方便查找,图书管理员一般会将书籍分门别类进行“存储”。按照一定规律编号,就是书籍这种“数据”的存储结构。

  • 算法:操作数据的一组方法

那我们如何来查找一本书呢?有很多种办法,你当然可以一本一本地找,也可以先根据书籍类别的编号,是人文,还是科学、计算机,来定位书架,然后再依次查找。笼统地说,这些查找方法都是算法。

从狭义上讲:

指某些著名的数据结构和算法,比如队列、栈、堆、二分查找、动态规划等。这些都是前人智慧的结晶,我们可以直接拿来用。我们要讲的这些经典数据结构和算法,都是前人从很多实际操作场景中抽象出来的,经过非常多的求证和检验,可以高效地帮助我们解决很多实际的开发问题。


20 个最常用的、最基础数据结构与算法:

  • 10 个数据结构:

数组链表队列散列表二叉树跳表Trie 树

  • 10 个算法:

递归排序二分查找搜索哈希算法贪心算法分治算法回溯算法动态规划字符串匹配算法


如何来衡量你编写的算法代码的执行效率呢?

数据结构和算法本身解决的是 “快”“省” 的问题,即如何让代码运行得更

快,如何让代码更省存储空间。

所以,执行效率是算法一个非常重要的考量指标。那如何来

衡量你编写的算法代码的执行效率呢? 这里就要用到我们今天要讲的内容: 时间、 空间复杂度分析

为什么需要复杂度分析?

1. 事后统计法:

把代码跑一遍,通过统计、监控,就能得到算法执行的时间和占用的内存大小

缺点

  • 1. 测试结果非常依赖测试环境

    测试环境中硬件的不同会对测试结果有很大的影响。比如,我们拿同样一段代码,分别用 Intel Core i9 处理器和 Intel Core i3 处理器来运行,不用说,i9 处理器要比 i3 处理器执 行的速度快很多。还有,比如原本在这台机器上 a 代码执行的速度比 b 代码要快,等我们 换到另一台机器上时,可能会有截然相反的结果

  • 2. 测试结果受数据规模的影响很大

    对同一个排序算法,待排序数据的有序度不一样,排序的执行时间就会有很大的差别。极端情况下,如果数据已经是有序的,那排序算法不需要做任何操作,执行时间就会非常短。除此之外,如果测试数据规模太小,测试结果可能无法真实地反应算法的性能。比如,对于小规模的数据排序,插入排序可能反倒会比快速排序要快!

    因此

    我们需要一个不用具体的测试数据来测试,就可以粗略地估计算法的执行效率的方法

2. 大 O 复杂度表示法:

算法代码执行的时间


文章作者: 孤雪飘寒
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 孤雪飘寒 !
  目录