什么是数据结构?什么是算法?
1. 入门:
从广义上讲:
- 数据结构:
指一组数据的存储结构
图书馆储藏书籍你肯定见过吧?为了方便查找,图书管理员一般会将书籍分门别类进行“存储”。按照一定规律编号,就是书籍这种“数据”的存储结构。
- 算法:
操作数据的一组方法
那我们如何来查找一本书呢?有很多种办法,你当然可以一本一本地找,也可以先根据书籍类别的编号,是人文,还是科学、计算机,来定位书架,然后再依次查找。笼统地说,这些查找方法都是算法。
从狭义上讲:
指某些著名的数据结构和算法,比如队列、栈、堆、二分查找、动态规划等。这些都是前人智慧的结晶,我们可以直接拿来用。我们要讲的这些经典数据结构和算法,都是前人从很多实际操作场景中抽象出来的,经过非常多的求证和检验,可以高效地帮助我们解决很多实际的开发问题。
20 个最常用的、最基础数据结构与算法:
- 10 个数据结构:
数组
、链表
、栈
、队列
、散列表
、二叉树
、堆
、跳表
、图
、Trie 树
;
- 10 个算法:
递归
、排序
、二分查找
、搜索
、哈希算法
、贪心算法
、分治算法
、回溯算法
、动态规划
、字符串匹配算法
。
如何来衡量你编写的算法代码的执行效率呢?
数据结构和算法本身解决的是
“快”
和“省”
的问题,即如何让代码运行得更
快,如何让代码更省存储空间。
所以,执行效率是算法一个非常重要的考量指标。那如何来
衡量你编写的算法代码的执行效率呢? 这里就要用到我们今天要讲的内容: 时间、
空间复杂度分析
。
为什么需要复杂度分析?
1. 事后统计法:
把代码跑一遍,通过统计、监控,就能得到算法执行的时间和占用的内存大小
缺点:
1. 测试结果非常依赖测试环境
测试环境中硬件的不同会对测试结果有很大的影响。比如,我们拿同样一段代码,分别用 Intel Core i9 处理器和 Intel Core i3 处理器来运行,不用说,i9 处理器要比 i3 处理器执 行的速度快很多。还有,比如原本在这台机器上 a 代码执行的速度比 b 代码要快,等我们 换到另一台机器上时,可能会有截然相反的结果
2. 测试结果受数据规模的影响很大
对同一个排序算法,待排序数据的有序度不一样,排序的执行时间就会有很大的差别。极端情况下,如果数据已经是有序的,那排序算法不需要做任何操作,执行时间就会非常短。除此之外,如果测试数据规模太小,测试结果可能无法真实地反应算法的性能。比如,对于小规模的数据排序,插入排序可能反倒会比快速排序要快!
因此:
我们需要一个不用具体的测试数据来测试,就可以粗略地估计算法的执行效率的方法
2. 大 O 复杂度表示法:
算法代码执行的时间