02 复杂度分析_pythoner学习数据结构与算法系列

系列目录

思维导图

基本概念

• 算法： 解决一个问题的完整性描述
• 算法的效率：

- 时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的使用程度。
- 空间复杂度：评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。

设计算法时，时间复杂度要比空间复杂度更容易出问题，所以一般情况一下我们只对时间复杂度进行研究。一般面试或者工作的时候没有特别说明的话，复杂度就是指时间复杂度。

七种常见时间复杂度

• O(1):Constant Complexity 常数复杂度
• O(log n):Logarithmic Complexity 对数复杂度
• O(n):Linear Complexity 线性复杂度
• O(n^2):N square Complexity 平方复杂度
• O(n^3):N cube Complexity 立方复杂度
• O(2^n):Exxponential Growth 指数复杂度
• O(n!): Factorial 阶乘复杂度

【1】映射

O 表示它的复杂度是关于n的什么一个函数，可以理解为映射，

类似于函数里的f(x)，f表示的是关于x的一种映射关系

【2】时间复杂度不考虑系数k，例：

• ① 只要是常数次的就是 O(1),不单指运算1次 可能是2次、3次、、、etc
• ② O(n)不单指运算n次，也可能是2n次、3n次、、、etc

时间复杂度分析

分析方法：

通过一段代码 根据n的不同情况，会运行多少次，来判断该段代码的时间复杂度

样例分析：

一 、O(1):Constant Complexity 常数复杂度

#不论n=？，只执行一次print
#即print(或者循环体代码)执行次数相对n的映射关系是常数C
#即print(或者循环体代码)执行次数不受n值得影响
def f  (n=100):
	print("你输入的是：",n)

#print 3次，时间复杂度是O(1)|常熟复杂度，没有 O(3)这种说法
#不论n=？，只执行3次print
def f  (n=100):
	print("你输入的是：",n)
	print("你需要输入的是：",n)
	print("你已经完成了：",n)

二、O(n):Linear Complexity 线性时间复杂度

#假设 print执行次数为y
#则执行次数y与输入n满足：y=n的线性关系
#print(或循环体代码)时间复杂度是O(n)
#或称为Linear Complexity 线性时间复杂度
def f  (n=10):
	for i in range(n):
		print("当前是第{}次执行".format(i))
		
#while写法
def f  (n=10,i=1):
    while i <=n:
        print("当前是第{}次执行".format(i))
        i+=1

三、O(n^2):N square Complexity 平方

#嵌套循环
#同理，假设 print执行次数为y
#则执行次数y与输入n满足：y=n^2的线性关系
#print(或循环体代码)时间复杂度是O(n^2)
#或称为N square Complexity 平方时间复杂度
def f(n=5):
    for i in range(n):
        for j in range(n):
            print("当前是第{}组，第{}次".format(i,j))

如果是i,j,k三层嵌套就是O(n^3) 立方的时间复杂度

#拓展———两个并列循环——O(n)线性时间复杂度
#print执行次数为y与输入n满足的是：y=2n的线性关系
#时间复杂度不考虑系数k,所以还是O(n)线性时间复杂度
def f(n=5):
    for i in range(n):
    	print(i)
    for j in range(n):
        print(j)

四、O(log n):Logarithmic Complexity 对数复杂度

#O(log n)的时间复杂度，
#或者O(log2(n)+1)的时间复杂度，不考虑常数项O(log n)
def f(n=100):
	i=1
	while i <n:
	    print(i)
	    i=i*2

归纳推导：

• 所以对数的实际映射通项应该是O(logk(n)+C)
• 上例中 i=i*2 的2换为3，时间复杂度就是O(log3(n)+1)

TIPS:关于python中的log函数

#log在python中的简单计算
#默认log=ln,其他底用logk()表示
import numpy  as np
import  math
print(math.log(4))
print(math.log10(100),np.log10(100))
print(math.log2(4),np.log2(4))
print(math.log(np.e),np.log(np.e))

五、O(2^n):Exxponential Growth 指数复杂度

#Fibonacci斐波那契数列
#指数复杂度通项O(k^n)，Fibonacci是O(2^n)
#详细分析过程见下一段：递归下的时间复杂度分析
def fib(n):
    if  n<=2:
        return n
    else:
        return fib(n-1)+fib(n-2)

递归下的时间复杂度分析

一、画递归树/状态树

求Fibonacci的第n项 ：F(n)=F(n-1)+F(n-2)

暴力解法： 直接递归，代码见上段：指数复杂度，时间复杂度 O(2^n)

F(6)的状态树:

• 每多展开一层，节点数就是上一层的两倍
• 总节点数就是2^n（指数级增长）

优化：

• 很多重复结果多次计算冗余；
• 可以加一个中间缓存，把中间结果缓存下来；
• 或者直接使用一个循环来写；

二、主定理（Master theorem）

主定理主要是用来解决所有递归函数时间复杂度计算 任何分治或者递归的函数都可以用主定理计算出时间复杂度

常见的四种场景：

• 一维的二分查找 O(logn)
• 二叉树遍历O(n)：每个节点都会访问且仅访问一次
• 二维矩阵（有序）的二分查找O(n)
• 归并排序——所有排序的时间复杂度都是O(nlogn)

三、常见面试题

1.二叉树的遍历-前序、中序、后序 :时间复杂度是多少？ 2.图的遍历，时间复杂度是多少？

• O(n)，n代表二叉树的节点总数
• 通过主定理得到
• 或者遍历（不论前、中、后序），每个节点都会访问且仅访问一次， 复杂度是线性于树的节点数的，所以是 O（n）的时间复杂度
• 同理(图的节点也是每个都会访问且仅访问一次)：图的遍历， 时间复杂度也是O(n)，n是图的结点总数

搜索算法：DFS(深度优先搜索)、BFS(广度优先搜索),时间复杂度是多少？

• 不论DFS还是BFS时间复杂度都是 O(n)，n是空间结点总数，每个节点都要 访问且仅访问一次

二分查找：时间复杂度是多少？

• 一维数组的二分查找是O(logn)
• 有序二维矩阵的二分查找是O(n)

时间复杂度曲线图

程序员职业素养：

• 一定要对自己程序的时间和空间复杂度有所了解，并养成习惯，写完每段代码之后，能够下意识地分析出你这段代码的时间和空间复杂度
• 能够用最简洁的时间和空间复杂度完成这段程序是顶尖职业选手必备的素养

时间复杂度优化

时间复杂度优化的简单样例，体验不同程序达成同一个目标的时间复杂度变化

题目：1+2+3+…+n

#解法一：暴力法累加
#时间复杂度 O(n)
def add_n(n):
	result = 0
	for i in range(1,n+1):
		result+=i
	return result

#解法二：求和公式 sum = n(n+1)/2
#时间复杂度 O(1)
#注意此处不是n^2的复杂度
def add_n(n):
	return n*(n+1)/2

一个好的时间复杂度程序，可以大大降低工程成本，提升工程效率

延伸性阅读资料

• 算法的时间复杂度和空间复杂度
• 如何理解算法时间复杂度的表示法
• Master theorem
• 主定理

上一篇: 01 数据结构与算法总览

下一篇: 03 数组、链表、跳表