【手把手带你刷Leetcode力扣】1.算法的时间与空间复杂度

什么是时间复杂度

算法的执行效率
算法的执行时间与算法的输入值之间的关系

def test(num): # N
	total = 0 # a
	for i in range(num):
		total += i # b
	return total # c

a+Nb+c
忽略常量
忽略系数

• O(N)

常见时间复杂度案例分析

for/while

• O(1)

def O1(num):
	i = num
	j = num*2
	return i+j

• O(logN) - 二分查找法

def OlogN(num): # N
	i = 1
	while (i<num):
		i = i*2 # 2^x=N
	return i

• O(M+N)

def OMN(num1, num2):
	total = 0
	for i in range(num1):
		total += i
	for j in range(num2):
		total += j
	return total

• O(N*logN) - 排序

def ONLogN(num1, num2):
	total = 0
	for i in range(num1):
		j = 1
		while(j < num2):
			total += i + j
			j = j * 2
	return total

• O(N^2)

def ON2(num):
	total = 0
	for i in range(num):
		for j in range(num):
			total += i + j
	return total

对比

O(1) < O(logN) < O(N) < O(N*logN) < O(N^2) < O(2^N) < O(N!)

什么是空间复杂度

算法的存储空间与输入值之间的关系

• O(1)

def test(num):
	total = 0
	for i in range(num):
		total += i
	return total

常量

• O(N)

def test(num): # List array
	array = []
	for num in nums:
		array.append(num)
	return array

看变量
递归栈O(N)

常用空间复杂度

O(1) < O(N) < O(N^2)

Note

时间和空间只能二选一
面试时：两种讲清楚
工作时：时间优先空间

学习视频来源B站—爱学习的饲养员—手把手带你刷Leetcode力扣