数据结构与算法之美(笔记)

目录
警告
本文最后更新于 2023-03-09,文中内容可能已过时。

本文章为极客时间上王争老师的《数据结构与算法之美》学习笔记,图片截取自该专栏。

入门篇

01-为什么要学数据结构与算法?

目的:建立时间复杂度、空间复杂度意识,写出高质量的代码,能够设计基础架构,提升编程技能,训练逻辑思维,积攒人生经验。

02-如何抓住重点,系统高效的学习数据结构与算法?

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

  • 广义:数据结构就是指一组数据的存储结构,算法就是操作数据的一组算法。
  • 狭义:指某些著名的数据结构与算法,比如队列、栈、堆、二分查找、动态规划等。

数据结构和算法的关系:

数据结构和算法是相辅相成的。数据结构是为算法服务的,算法要作用在特定的数据结构之上。

学习重点:

  • 首先要掌握一个数据与算法中最重要的概念——复杂度分析

    数据结构和算法解决的是如何更省、更快地存储和处理数据的问题,因此,我们就需要一个考量效率和资源消耗的方法,这就是复杂度分析方法。

img

10个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树。

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

一些事半功倍的学习技巧:

  1. 边学边练,十度刷题。
  2. 多问、多思考、多互动。
  3. 打怪升级学习方法。
  4. 知识需要沉淀,不要想视图一下子掌握所有。

03-复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?

复杂度分析是整个算法学习的精髓,只要掌握了他,数据结构与算法的内容基本上就掌握了一半。

为什么需要复杂度分析?

  1. 测试结果非常依赖测试环境
  2. 测试结果受到数据规模的影响很大

大O复杂度表示法

$T~(n)~ =O(f~(n)~)$

其中:$T~(n)$表示代码执行的时间;n表示数据规模的大小;$f(n)~$表示每行代码执行的次数总和。

大O时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

例如:

1
2
3
4
5
6
7
8
int cal(int n) {
    int sum = 0;	1*unit_time
    int i = 1;		1*unit_time
    for( ; i <= n; ++i) {	n*unit_time
        sum = sum + i;		n*unit_time
    }
    return sum;
}

假设:每行代码执行的时间都是一样的,为一个单位时间(unit_time)。

即:$T~(n)~=(2n+2)*unit_time$

时间复杂度分析:

  1. 只关注循环执行次数最多的一段代码。

    通常会忽略掉公式中的常量、低阶、系数,只需要记录一个最大阶的量级即可。

  2. 加法法则:总复杂度等于量级最大的那段代码的复杂度。

  3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

几种常见时间复杂度示例分析

img

把时间复杂度为非多项式量级的算法问题叫作NP(Non-Deterministic Polynomial,非确定多项式)问题。其中非多项式量级只有两个:$O(2^n)$和O(n!)。

1. O(1)

一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1)。

2. O(logn)、O(nlogn)

在对数阶时间复杂度的表示方法里,我们忽略对数的“底”,统一表示为O(logn)。

如果一段代码的时间复杂度是O(logn),我们循环执行n遍,时间复杂度就是O(nlogn)了。而且,O(nlogn)也是一种非常常见的算法时间复杂度。比如,归并排序、快速排序的时间复杂度都是O(nlogn)。

3. O(m+n)、O(m*n)

代码的复杂度有两个数据的规模来确定。

O(m+n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

O(m*n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int cal(int m, int n) {
  int i = 1;
  int j = 1;
  int sum;
  for (; i < m; ++i) {
    for (; j < n; ++j) {
    	sum = sum + i*j;
  	}
  }
  return sum;
}

空间复杂度分析

空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系。

常见的空间复杂度就是O(1)、O(n)、$O(n^2)$,像O(logn)、O(nlogn)这样的对数阶复杂度平时都用不到。

img

04-复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度?

最好情况时间复杂度(best case time complexity)、最坏情况时间复杂度(worst case time complexity)、平均情况时间复杂度(average case time complexity)、均摊时间复杂度(amortized time complexity)。

  • 最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度。
  • 最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度。

基础篇

05-数组:为什么很多编程语言中数组都从0开始编号?

06-链表(上):如何实现LRU缓存淘汰算法?

07-链表(下):如何轻松写出正确的链表代码?

08-栈:如何实现浏览器的前进和后退功能?

09-队列:队列在线程池等有限资源池中的应用

10-递归:如何三行代码找到“最佳推荐人”?

11-排序(上):为什么插入排序比冒泡排序更受欢迎?

12-排序(下):如何使用快排思想在O~(n)~ 内查找第K大元素?

13-线性排序:如何根据年龄给100万用户数据排序?

14-排序优化:如何实现一个通用的、高性能的排序函数?

15-二分查找(上):如何最省内存的方式实现快速查找功能?

16-二分查找(下):如何快速定位IP对应的省份地址?

17-跳表:为什么Redis一定要用跳表来实现有序集合?

18-散列表(上):Word文档中的单词拼写检查功能是如何实现的?

19-散列表(中):如何打造一个工业级水平的散列表?

20-散列表(下):为什么散列表和链表经常会一起使用?

21-哈希算法(上):如何防止数据库中的用户信息被脱裤?

22-哈希算法(下):哈希算法在分布式系统中有哪些应用?

23-二叉树基础(上):什么样的二叉树适合用数组来存储?

24-二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?

25-红黑树(上):为什么工程中都用红黑树这种二叉树?

26-红黑树(下):掌握这些技巧,你也可以实现一个红黑树?

27-递归树:如何借助树来求解递归算法的时间复杂度?

28-堆和堆排序:为什么说堆排序没有快速排序快?

29-堆的应用:如何快速获取到top10最热门的搜索关键字?

30-图的表示:如何存储微博、微信等社交平台网络中的好友关系?

31-深度和广度优先搜索:如何找出社交网络中的三度好友关系?

32-字符串匹配基础(上):借助哈希算法实现高效字符串匹配?

33-字符串匹配基础(中):如何实现文本编辑器中的查找功能?

34-字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?

35-Trie树:如何实现搜索引擎的搜索关键词提示功能?

36-AC自动机:如何用多模式串匹配实现敏感词过滤功能?

37-贪心算法:如何使用贪心算法实现Huffman压缩编码?

38-分治算法:谈一谈大规模计算框架MapReduce中的分治思想

39-回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想

40-初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?

41-动态规划理论:一篇文章带你彻底搞懂最优子结构,无后效性和重复子问题

42-动态规划实战:如何实现搜索引擎中的拼写纠错功能?

高级篇

43-拓扑排序:如何确定代码源文件的编译依赖关系?

44-最短路径:地图软件是如何计算出最优出行路径的?

45-位图:如何实现网页爬虫中的URL去重功能?

46-概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?

47-向量空间:如何实现一个简单的音乐推荐系统?

48-B-树:MySQL数据库索引是如何实现的?

49-搜索:如何用A*搜索算法实现游戏中的寻路功能?

50-索引:如何在海量的数据中快速查找某个数据?

51-并行算法:如何利用并行处理提高算法的执行效率?

实战篇

52-算法实战(一):剖析Redis常用数据类型对应的数据结构

53-算法实战(二):剖析搜索引擎背后的经典数据结构和算法

54-算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法

55-算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法

56-算法实战(五):如何利用学过的数据结构和算法实现一个短网址系统?

Buy Me a Coffee ~~
hiifong 支付宝支付宝
hiifong 微信微信
0%