时间复杂度
算法的执行效率，算法执行时间与算法输入值之间的关系
def test(num):
total=0
for i in range(num):
total+=i
return total
# 大O表示法中不关心系数和两个小的时间复杂度。
# 该算法的时间复杂度为O(N)一般看时间复杂度查看算法中有没有for/while循环 无循环一般都为O(1)
# 案例分析
# O(1)
def O1(num):
i = num
j = num*2
return i+j
# O(logN)
def OlogN(num):
i=1
while(i<num):
i=i*2
return i
# O(N)
def ON(num):
total=0
for i in range(num):
total+=i
return total
# 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(NlogN)
def ONlogN(num1,num2):
total=0
j=0
for i in range(num1):#N
while(j<num2):#logN
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(1)<O(logN)<O(N)<O(NlogN)<O(N^2)<O(2^N)<O(N!)
二分查找：O(logN),排序：O(NlogN)
算法的空间复杂度
大O表示法
算法存储空间与输入值之间的关系
def test(num):
total=0 #变量占空间了，空间复杂度O(1)
for i in range(num):
total+=i
return total
# 空间复杂度O(1) 一个int型占四个字节，一直不变的
def test(nums):
array=[] #声明了列表变量
for num in nums:
array.append(num)
return array
#空间复杂度O(N)占空间的都是声明的变量，1.看空间复杂度直接找变量
变量如果是常量，就是O(1)，里面有多个数据，随着输入改变变化时候，就是O(N),eg:array list等等。
常用空间复杂度O(1),O(N)
很少有O(N^2)
2.看有无递归，每一层信息都保留在递归栈，递归一般都有空间复杂度O(N)
总结：时间复杂度和空间复杂度只能二选一，鱼和熊掌不可兼得。可以写出两种不同的程序，工作时候时间复杂度>空间复杂度
