算法概述
Best Practices
Top tips
-
算法：在计算机领域里，算法是一系列程序指令，用于处理特定的运算和逻辑问题
衡量算法优劣的主要标准是时间复杂度和空间复杂度
-
数据结构：数据的组织、管理和存储格式，其使用目的是为了高效的访问和修改数据
数据结构包含数组、链表这样的线性数据结构，也包含树、图这样的复杂数据结构
-
时间复杂度：对一个算法运行时间长短的量度，用大O标识，记作T(n)=O(f(n))
常见的时间复杂度按照从低到高的顺序，包括O(1)、O(log n)、O(n)、O(n²)、O(n³)、O(2^n)、O(n!)
-
空间复杂度：对一个算法在运行过程中临时占用存储空间大小的量度，用大O表示，记作S(n)=O(f(n))
常见的空间复杂度按照从低到高的顺序，包括O(1)、O(n)、O(n²)等。其中递归算法的空间复杂度和递归深度成正比
时间复杂度
主定理
-
二分查找：数列本身有序，并在这个有序的数列找到你要的数，每次都一分为二，只查一边（O(log n)）
-
二叉树遍历：每次要一分为二，每一边都是相等的时间复杂度（O(n)）
二叉树遍历每一个节点都访问一次且仅访问一次
-
已排序的二维矩阵：二分查找，一维数组查找（O(log n)），二维矩阵查找（O(n)）
-
归并排序：排序最优的办法（O(n log n)）
思考题
-
二叉树遍历-前序、中序、后序：时间复杂度是多少？
（O(n)）n代表二叉树里面的节点总数
不管是前序、中序、后序，它遍历二叉树的时候，每个节点都会访问一次且仅访问一次，所以它的时间复杂度就是线性于二叉树的节点总数，也就是（O(n)）的时间复杂度
-
图的遍历：时间复杂度是多少？
（O(n)）n代表图的节点总数
图里面的每一个节点访问一次且仅访问一次，所以时间复杂度为（O(n)）
-
搜索算法：DFS、BFS时间复杂度是多少？
（O(n)）n代表搜索空间的节点总数
DFS(深度优先)、BFS（广度优先），每一个节点只访问一次，所以时间复杂度为（O(n)）
-
二分查找：时间复杂度是多少？
（O(log n)） 每次都一分为二，只查一边
空间复杂度
-
数组的长度
数组的长度基本上就是空间复杂度，一维数组O(n)、二维数组O(n²)
-
递归的深度
递归最深的深度就是空间复杂度的最大值
练习
爬楼梯
“变位词”判断问题
”变位词“：两个词之间存在组成字母的重新排列关系
-
逐字检查
解法思路：将词1中的字符逐个到词2中检查是否存在，存在就”打勾“标记（防止重复检查）。如果每个字符都能找到，则两个词就是变位词，只要有1个字符找不到，就不是变位词
程序技巧：实现“打勾”标记：将词2对应字段设为None，由于字符串是不可变类型，需要先复制到列表中
时间复杂度：O(n²)
def anagramSolution1(s1, s2): alist = list(s2) pos1 = 0 stillOK = True while pos1 < len(s1) and stillOK: pos2 = 0 found = False while pos2 < len(alist) and not found: if s1[pos1] == alist[pos2]: found = True else: pos2 += 1 if found: alist[pos2] = None else: stillOK = False pos1 += 1 return stillOK print(anagramSolution1("abcd", "dcba")) -
排序比较
解法思路：将两个字符串都按照字母顺序排好序，再逐个字符对比是否相同，如果相同则是变位词，有任何不同就不是变位词时间复杂度：O(n log n)
def anagramSolution1(s1, s2): alist1 = list(s1) alist2 = list(s2) alist1.sort() alist2.sort() pos = 0 matches = True while pos < len(s1) and matches: if alist1[pos] == alist2[pos]: pos += 1 else: matches = False return matches print(anagramSolution1("abcd", "dcba")) -
暴力法
解题思路：穷尽所有可能组合。将s1中出现的字符进行全排列，再查看s2是否出现在全排列列表中，根据组合数学结论，如果n个字符进行全排列，其所有可能得字符串个数为n!
-
计数比较
解题思路：对比两个词中每个字母出现的次数，如果26个字母出现的次数都相同的话，这两个字符串就一定是变位词
时间复杂度：O(n)
def anagramSolution1(s1, s2): c1 = [0] * 26 c2 = [0] * 26 for i in range(len(s1)): pos = ord(s1[i]) - ord('a') c1[pos] = c1[pos] + 1 for i in range(len(s2)): pos = ord(s2[i]) - ord('a') c2[pos] = c2[pos] + 1 j = 0 stillOK = True while j < 26 and stillOK: if c1[j] == c2[j]: j += 1 else: stillOK = False return stillOK print(anagramSolution1("abcd", "dcba"))
Python数据类型的性能
| 类型 | list | dict |
|---|---|---|
| 索引 | 自然数i | 不可变类型值key |
| 添加 | append、extend、insert | b[k]=v |
| 删除 | pop、remove* | pop |
| 更新 | a[i]=v | b[k]=v |
| 正查 | a[i]、a[i:j] | b[k]、copy |
| 反查 | index(v)、count(v) | 无 |
| 其它 | reverse、sort | has_key、update |
创建一个Timer对象，指定需要反复运行的语句和只需要运行一次的“安装语句”
然后调用这个timeit方法，其中可以指定反复运行多少次
from timeit import Timer
def test1():
l = []
for i in range(1000):
l = l + [i]
def test2():
l = []
for i in range(1000):
l.append(i)
def test3():
l = [i for i in range(1000)]
def test4():
l = list(range(1000))
t1 = Timer("test1()", "from __main__ import test1")
print(f"concat {t1.timeit(number=1000)} seconds\n")
t2 = Timer("test2()", "from __main__ import test2")
print(f"append {t2.timeit(number=1000)} seconds\n")
t3 = Timer("test3()", "from __main__ import test3")
print(f"comprehension {t3.timeit(number=1000)} seconds\n")
t4 = Timer("test4()", "from __main__ import test4")
print(f"list range {t4.timeit(number=1000)} seconds\n")
列表时间复杂度
字典时间复杂度
- 可见字典的执行时间与规模无关，是常数
- 而列表的执行时间则随着列表的规模加大而线性上升
import timeit
import random
for i in range(10000, 1000001, 20000):
t = timeit.Timer(f"random.randrange({i}) in x", "from __main__ import random,x")
x = list(range(i))
lst_time = t.timeit(number=1000)
x = {j:None for j in range(i)}
d_time = t.timeit(number=1000)
print(f"{i,lst_time,d_time}")
参考链接