- 数据结构与算法 (Python 版)
- 知识点一 : 算法的概念
- 知识点二 : 时间复杂度
- 知识点三 : 空间复杂度
- 知识点四 : 递归
- 知识点五 : 递归算法:汉诺塔问题
- 1.题目
- 2.思路
- 3.代码
- 4.小结
- 知识点六 : 查找
- 1.顺序查找
- 2.二分查找
- 知识点七 : 排序
- 1.冒泡排序
- 2.选择排序
- 3.插入排序
- 4.快速排序
- 5.堆排序
1.概述:
1.1 算法 (Algorithm)即一个计算过程, 即用来解决问题的方法.
1.2 著名 IT 科学家尼古拉斯·沃斯 (Niklaus Wirth) 认为 " 程序 = 数据结构 + 算法 "
1.概述:
1.1 时间复杂度: 用来评估算法运行效率的一个式子 ( 即用一个类似于公式的东西能够形象的比较两个算法的快慢 )
1.2 为什么不使用时间来体现算法的运行快慢?
- 电脑本身内存的运行效率有差异.
- 执行代码的次数有差异.(如for循环1次,10次,100次都有所不同)
2.案例:
2.1 打印一行代码
我们将一个print定义为叫O(1),我们将O理解为一个约等号,大约的意思,括号中的东西就类似于单位,1就是一个单位,类似于秒这个单位,但不是1秒,而就是1,它没有后缀.
# 只执行了一次,时间消耗大约为1,即O(1)
print("Hello World")
2.2 打印一个for循环
# i执行n次, 时间消耗大约为 1×n, 即O(n)
for i in range(n):
print("Hello World")
2.3 打印两个for循环
# i执行1次时,j执行n次 时间消耗大约为 1×n,即O(n)
# 然而i本身还要执行n次,所以是 n×(1×n), 最终的执行时间为 O(n^2)
for i in range(n):
for j in range(n):
print("Hello World")
2.4 打印三个for循环
# 同两个for循环,for循环执行n次即时间消耗O(n),三次循环即 n×n×n,故最终的消耗时间为O(n^3)
for i in range(n):
for j in range(n):
for k in range(n):
print("Hello World")
2.5 打印三行代码
# 执行三次,因为执行三次print和执行一次print的的差距几乎忽略不计,时间复杂度 O(1)
# 因为按正常逻辑来说,执行三次print的时间复杂度本来应是3×1 即O(3)
# 但是因为时间复杂度的低精度性,就直接被约算成了O(1)
print("Hello World")
print("Hello Python")
print("Hello Algorithm")
注意点1 : 执行基本操作,只要它的问题规模不上升到n这么大的时候,它的时间复杂度就是O(1)
(就像是我们睡觉只会说大约睡了几个小时,而不是说睡了几个小时几分几秒.)注意点2 : 时间复杂度是一个低精度的计算方式, 只算一个大致的内容即可.
2.6 打印双重for-print循环
# 同理两次for循环应该是n^2,又因为多打印了n次Hello World
# 正常来说,时间复杂度应该是O(n^2+n)
# 但是同样是因为时间复杂度的低精度性,故而这里的时间复杂度应该是O(n^2)
for i in range(n):
print("Hello World")
for j in range(n):
print("Hello World")
2.7 打印减半while循环
# 当n=64时输出:64,32,16,8,4,2
# 代码每执行一次,n的值都比之前少一半
# 2^6 = 64 → 1og~2~64 = 6
# 所以将时间复杂度记为O(log~2~n) 或 O(logn)
# 循环减半logn
while n > 1:
print(n)
n = n // 2
3.总结:
3.1 时间复杂度是用来估计算法运行时间的一个式子 (单位).
3.2 一般来说 (即在基本上相同条件下), 时间复杂度高的算法比复杂度低的算法慢.
3.3 常见的时间复杂度 (按效率排序):
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n2logn) < O(n3 )
3.4 复杂问题的时间复杂度:
O(n!) O(2n) O(nn) …
3.5 快速判断算法复杂度 (适用于绝大多数简单情况,复杂情况需要根据算法执行过程判断):
- 确定问题规模 n → 如列表排序,需要先确定列表的长度
- 循环减半过程 → logn
- k 层关于 n 的循环 → nk (几层循环就是n的几次方)
1.概述:
1.1 空间复杂度: 用来评估算法内存占用大小的式子
(小电影100MB能看就不要去下300MB的看，代码同理，能用10MB解决的问题就不要用30MB存储去多占用空间.)
1.2 空间复杂度表示:
- 算法使用了几个变量: O(1)
- 算法使用了长度为 n 的一维列表: O(n)
- 算法使用了 m 行 n 列的二维列表: O(mn)
(空间复杂度一般来说有O(1)、O(n)、O(n2)、O(logn)、O(NlogN)几种.但是其实最常用的也就是O(1) 或者 O(n)，用到O(n2)的情况都不多)
1.3 空间换时间:
在我们写算法时，时间复杂度和空间复杂度只能二选一进行优化，但最好是优化时间复杂度，毕竟在这个学习资料都要放3个T的时代，存储空间并不算昂贵，但是时间真的很宝贵。故而优化时:时间复杂度>空间复杂度.
1.概述:
1.1 递归的两个特点:
- 调用自身
- 结束条件
2.实例:
2.1 先打印后递归
# 标准递归函数:先打印后递归
def func1(x):
if x > 0: # 1.有结束条件
print(x)
func1(x-1) # 2.调用自身
func1(3)
2.2 先递归后打印
# 标准递归函数: 先递归后打印
def func2(x):
if x > 0: # 1.有结束条件
func2(x-1) # 2.调用自身
print(x)
func2(3)
原版: 汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞n片黄金圆盘。大梵天命令婆罗门把圆盘从下自上开始、按大小顺序重新摆放在另一根柱子上。并且规定，小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘，如图所示。问应该怎样移动，才能将圆盘移动到另一根柱子上。
数学版: 从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数。
(1) 假设 n = 2 时:
第一步: 把 圆盘1 从 A 移动到 B
第二步: 把 圆盘2 从 A 移动到 C
第三步: 把圆盘1 从 B 移动到 C
(2) 假设有n个盘子时:
第一步: 把 n-1 个圆盘 从 A 经过 C 移动到 B
第二步: 把 第n个圆盘 从 A 移到 C
第三步: 把 n-1 个圆盘 从 B 经过 A 移到到 C
# -*- coding: utf-8 -*-
# 定义一个有参无返回值函数,n是圆盘个数, abc分别对应ABC三柱
def HanNuoTa(n, a, b, c):
if n > 0:
# 1.把 n-1 个圆盘 从 A 经过 C 移动到 B
HanNuoTa(n - 1, a, c, b)
# 2.把 第n个圆盘 从 A 移到 C
print(f"moving from {a} to {c}")
# 3.把 n-1 个圆盘 从 B 经过 A 移到到 C
HanNuoTa(n - 1, b, a, c)
HanNuoTa(3, 'A', 'B', 'C')
- 汉诺塔移动次数的递推式: h(x) = 2h(x-1) + 1
- h (64) =18446744073709551615
- 假设婆罗门每秒钟搬一个盘子,则总计需要5800亿年
- 查找 : 在一些数据元素中, 通过一定的方法找出与给定关键字相同的数据元素的过程.
- 列表查找 ( 线性表查找 ) : 从列表中查找指定元素
- 输入 : 列表、待查找元素
- 输出 : 元素下标 ( 未找到元素时一般返回None或-1 )
- 内置列表查找函数 : index( )
- 顺序查找 ( Linear Search ) : 也称线性查找, 从列表第一个元素开始顺序进行搜索, 直到找到元素或搜索到列表最后一个元素为止.
- 顺序查找时间复杂度 : O(n)
# -*- coding: utf-8 -*-
def linear_search(li, val):
# enumerate(teration, start): 枚举函数, 默认包含两个参数.
# 1.iteration参数:需要遍历的参数 (如字典、列表、元组等)
# 2.start参数:开始的参数，默认为0（不写start那就是从0开始）
# 3.enumerate函数有两个返回值，第一个返回值为从start参数开始的数，第二个参数为iteration参数中的值。
for index, value in enumerate(li):
if value == val:
return index
else:
return None
-
二分查找 (Binary Search) : 也称折半查找, 针对一个有序数据集合, 每次都通过跟区间的中间元素对比, 将待查找的区间缩小为之前的一半, 直到找到要查找的元素, 或者区间被缩小为 0.
-
二分查找图解 : 从列表中查找元素3.
-
二分查找时间复杂度 : O(logn)
-
二分查找与顺序查找比较 : 二分查找的效率远高于顺序查找.
-
二分查找的局限性 :
- 二分查找针对的是有序数据, 也就是说我们使用二分查找前必须对数据进行排序.
- 数据量太小和太大都不适用于二分查找, 太小可以直接用顺序查找, 太大电脑内存撑不住.
# -*- coding: utf-8 -*-
def binary_search(li, val):
left = 0
right = len(li) - 1
# 候选区有值
while left <= right:
mid = (left + right) // 2
if li[mid] == val:
return mid
# 待查找的值在mid左侧
elif li[mid] > val:
right = mid - 1
# 待查找的值在mid右侧
else:
left = mid + 1
else:
return None
-
排序 : 将一组 “无序” 的记录序列调整为 “有序” 的记录序列
-
列表排序 : 将无序列表变为有序列表
- 输入 : 列表
- 输出 : 有序列表
-
升序与降序
- 升序 : 按从小到大的顺序排列 (如1、3、5、6、7、9)
- 降序 : 按从大到小的顺序排列 (如9、8、6、4、3、1)
-
内置排序函数 : sort( )
-
常见排序算法 :
排序 Low B 三人组 排序NB三人组 其他排序 1.冒泡排序 1.快速排序 1.希尔排序 2.选择排序 2.堆排序 2.计数排序 3.插入排序 3.归并排序 3.基数排序
-
冒泡排序 (Bubble Sort):
- 列表每两个相邻的数, 如果前面比后面大, 则交换这两个数
- 一趟排序完成后, 则无序区减少一个数, 有序区增加一个数
- 代码关键点 : 趟、无序区范围
- 执行 n-1 趟 ( n是列表的长度 )
-
冒泡排序的时间复杂度 : O(n2)
-
冒泡排序实例 :
初始数据：[ 30,13,25,16,47,26,19,29,10 ]
第一趟执行过程（先从30依次开始比较）：
0 1 2 3 4 5 6 7 8 13 30 25 16 47 26 19 29 10 13 25 30 16 47 26 19 29 10 13 25 16 30 47 26 19 29 10 13 25 16 30 47 26 19 29 10 13 25 16 30 26 47 19 29 10 13 25 16 30 26 19 47 29 10 13 25 16 30 26 19 29 47 10 13 25 16 30 26 19 29 10 47 第一趟 : [13 25 16 30 26 19 29 10 47]
第二趟：[13 16 25 26 19 29 10 30 47]
…
第八趟: [10 13 16 19 25 26 29 30 47]
注意点1 : 冒泡排序相当于是一个接力，从最左侧的一个 记录（30）开始从左到右开始比较，遇到比自己小的数就将其甩在身后（放到30的左边），遇到比自己大的数就把接力棒交给它（40），直到这一趟中的最大记录到达最右侧，然后开始新一轮接力跑（上一趟的最大记录不再参与此趟）
# -*- coding: utf-8 -*-
import random
def bubble_sort(li):
# 第i趟
for i in range(len(li) - 1):
for j in range(len(li) - i - 1):
exchange = False
# >是执行升序排序,<是执行降序排序
if li[j] > li[j + 1]:
li[j], li[j + 1] = li[j + 1], li[j]
exchange = True
# print(f"第{i+1}趟:{li}")
# if not exchange 的意思是 if not False,因为我们之前将False这个值赋给了exchange这个变量
if not exchange:
return
li = [random.randint(0, 100) for i in range(10)]
print(f"执行冒泡排序前:{li}")
bubble_sort(li)
print(f"执行冒泡排序后:{li}")
- 选择排序 (Select Sort) : 一趟排序记录最小的数, 将其放到第一个位置; 再一趟排序记录列表无序区最小的数, 放到第二个位置.
- 选择排序算法关键点 : 有序区和无序区、无序区最小数的位置
- 选择排序的时间复杂度 : O(n2)
# -*- coding: utf-8 -*-
# 选择排序简单版
# 缺陷:开辟了新的存储空间,算法的利用率低
import random
def select_sort_simple(li):
li_new = []
for i in range(len(li)):
min_val = min(li)
li_new.append(min_val)
li.remove(min_val)
return li_new
li = [random.randint(0,100) for i in range(10)]
print(f"执行简单选择排序前:{li}")
print(f"执行简单选择排序后:{select_sort_simple(li)}")
# -*- coding: utf-8 -*-
import random
# 选择排序完整版
def select_sort(li):
# i = 0,1,2,3,4,5,6,7,8
for i in range(len(li)-1):
min_loc = i
# i+1少比一次,因为我们设的最开始的最小值为i,相当于减少了它自己跟自己比的那一趟
# j = 1,2,3,4,5,6,7,8,9
for j in range(i+1, len(li)):
# 现在在li列表中j就是i的后一个下标,只要j对应的那个元素比i现在对应的那个元素小,两者就交换位置
if li[j] < li[min_loc]:
min_loc = j
li[i], li[min_loc] = li[min_loc], li[i]
# print(li)
li = [random.randint(0,100) for i in range(10)]
print(f"执行选择排序前:{li}")
select_sort(li)
print(f"执行选择排序后:{li}")
-
插入排序 (InsertionSort) : 每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止.
-
插入排序的时间复杂度 : O(n2)
-
插入排序图解 :
# -*- coding: utf-8 -*-
import random
def insert_sort(li):
# i表示摸到的牌的下标
for i in range(1, len(li)):
tmp = li[i]
# j表示手里的牌的下标
j = i - 1
while j >= 0 and li[j] > tmp:
li[j + 1] = li[j]
j -= 1
li[j + 1] = tmp
print(li)
li = [random.randint(0, 100) for i in range(10)]
print(f"执行插入排序前:{li}")
insert_sort(li)
print(f"执行插入排序后:{li}")
-
快速排序 (Quick sort) : 是对冒泡排序的一种改进.
-
快速排序思路:
- 取一个元素 p (第一个元素), 使元素p归位
- 列表被p分成两部分, 左边都比p小, 右边都比p大
- 递归完成排序
-
快速排序的时间复杂度: O(nlogn)
-
快速排序思路图解:
-
快速排序框架图解:
假设对以下10个数进行快速排序：
我们先模拟快速排序的过程：首先，在这个序列中随便找一个数作为基准数，通常为了方便，以第一个数作为基准数。
在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置是k。现在就需要寻找这个k，并且以第k位为分界点，左边的数都≤ 6，右边的数都≥ 6。那么如何找到这个位置k呢？
我们要知道，快速排序其实是冒泡排序的一种改进，冒泡排序每次对相邻的两个数进行比较，这显然是一种比较浪费时间的。
而快速排序是分别从两端开始”探测”的，先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i 指向序列的最左边，指向数字6。让哨兵j指向序列的最右边，指向数字8。
首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要。哨兵j一步一步地向左挪动（即j = j − 1），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i = i + 1），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i ii停在了数字7面前。
现在交换哨兵 i i i和哨兵 j j j所指向的元素的值。交换之后的序列如下。
到此，第一次交换结束。接下来开始哨兵j 继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4 < 6，停下来。哨兵i ii也继续向右挪动的，他发现了9 > 6，停下来。此时再次进行交换，交换之后的序列如下。
第二次交换结束。哨兵j jj继续向左挪动，他发现了3 < 6，又停下来。哨兵i 继续向右移动，此时哨兵i 和哨兵j 相遇了，哨兵i 和哨兵j 都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下。
到此第一轮“探测”真正结束。现在基准数6已经归位，此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i ii和j jj碰头为止。
现在我们将第一轮“探测"结束后的序列，以6为分界点拆分成两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。
重复第一轮的过程，应该得到如下序列：
OK，现在3已经归位。接下来需要处理3左边的序列：
处理之后，2已经归位，序列“1”只有一个数，也不需要进行任何处理，因此“1”也归位。
对于基数右边的序列，采用和左边相同的过程；最终将会得到这样的序列，如下。
快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序结束。
快速排序之所以比较快，是因为与冒泡排序相比，每次的交换时跳跃式的，每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是 O(n2)，它的平均时间复杂度为O(n log2n)。
# -*- coding: utf-8 -*-
import random
# 第一步:partition函数
def partition(li, left, right):
tmp = li[left]
while left < right:
# 从右边找比tmp小的数
while left < right and li[right] >= tmp:
# 往左走一步
right -= 1
# 把右边的值写到左边空位上
li[left] = li[right]
# print(li, "right")
while left < right and li[left] <= tmp:
left += 1
# 把左边的值写到右边的空位上
li[right] = li[left]
# print(li, "left")
# tmp归位
li[left] = tmp
return left
# 第二步:快速排序框架
def quick_sort(li, left, right):
# 至少要两个元素
if left < right:
mid = partition(li, left, right)
quick_sort(li, left, mid-1)
quick_sort(li, mid+1, right)
li = [random.randint(0, 100) for i in range(10)]
print(f"执行插入排序前:{li}")
quick_sort(li, 0, len(li) - 1)
print(f"执行插入排序后:{li}")
-
堆排序前置知识点1: 树
-
树是一种数据结构 (如目录结构) ,可以递归定义.
-
树是由 n 个节点组成的集合
- 如果 n = 0, 那么这是一棵空树 ;
- 如果 n > 0, 那么存在1个节点作为树的根节点, 其他节点可以分为 m 个集合, 每个集合本身又是一棵树
-
树的基本概念1: 节点
- 根节点 : 树最顶部的一个节点, 如节点A.
- 叶子节点: 树最末端的节点, 如节点B, C, H, I, P, Q, K, L, M, N
- 子节点: 除根节点之外, 并且本身下面还连接有节点的节点, 如节点D, E, J, F, G
-
树的基本概念2: 高度 / 深度
-
树的基本概念3: 树的度
-
树的基本概念4: 孩子节点 / 父节点
-
树的基本概念5: 子树
-
-
堆排序前置知识点2: 二叉树
-
二叉树: 度不超过2的树 (即分支不能多于两条)
- 二叉树每个节点资源的有两个孩子节点
- 二叉树有两个孩子节点时, 严格区分左孩子节点和右孩子节点
-
特殊形态的二叉树:
- 满二叉树: 一个二叉树如果每一个层的节点都达到最大值, 则这个二叉树就是满二叉树.
- 完全二叉树: 叶节点只能出现在最下层和次下层, 并且最下面一层的节点都集中在该层最左边的若干位置的二叉树.
-
二叉树的存储方法 (表示方式):
- 链式存储方式
- 顺序存储方式
-
-
堆: 一种特殊的完全二叉树结构
-
大根堆: 一棵完全二叉树, 满足任一节点都比其他孩子节点大
-
小根堆: 一棵完全二叉树, 满足任一节点都比其他孩子节点小
-
-
堆的向下调整性质:
-
假设根节点的左右子树都是堆,但根节点不满足堆的性质
-
可以通过一次向下的调整来将其变成一个堆
-
-
堆排序过程:
- 1.建立堆
- 2.得到堆顶元素,为最大元素
- 3.去掉堆顶,将堆最后一个元素放到堆顶, 此时可通过一次调整重新使堆有序
- 4.堆顶元素为第二大元素
- 5.重复步骤3,直到堆变空
