1. 时间复杂度
1. 时间复杂度是衡量一个算法运行所需的时间，是一个函数，由于执行时间需要经过测试才能得出，而算法执行的时间和执行次数成正比例关系，所以我们的时间复杂度根据算法的执行次数来确定。常见的时间复杂度：O(1) < O(logN) < O(N) < O(N logN) < O(N²) < O(N² log N) < O(N³)
例子1：时间复杂度为N²
def func(N): count = 0 for i in range(N): for j in range(N): count += 1 for k in range(N)： count += 1 for l in range(10): count += 1
该函数总共执行了：N² + N + 10 次
用大O渐进表示法来估算其大概结果：当N无限大时，N+10会对结果的影响越来越小，可以将其进行省略
即func的时间复杂度为O(N²)
例子2：时间复杂度为N
def func(N): count = 0 for k in range(N)： count += 1 for l in range(10): count += 1
该函数总共执行了：N + 10 次，时间复杂度为O(N)
例子3：时间复杂度为1
def func():
count = 0
for k in range(100)：
count += 1
该函数总共执行了：100 次，是一个常数，时间复杂度为O(1)
大O渐进表示法：
用常数1取代运行时间中的所有加法常数：O(n) = 1 + 2 + 3 + ... + N，N = 10，即运行次数O(n) = 55，是一个已知的常数，可以用O(1)表示
在运行次数的函数中，只保留最高阶：O(n) = N² + 2N + 10 ，保留最高阶，即O(N²)表示时间复杂度
如果最高阶项存在且不是1，则取出与这个项目相乘的常数：O(n) = 3N² + 5N + 101，则时间复杂度最终表示为 O(N²)
时间复杂度存在最好，平均和最坏的情况：通常用最坏的情况来表示该算法的时间复杂度
最好的情况：任意输入规模的最小运行次数(下界)，如N = 1
平均的情况：任意输入规模的期望运行次数，如N = N/2
最坏的情况：任意输入规模的最大运行次数(上界)，如N = N
二分算法的时间复杂度
二分算法：时间复杂度为O(logN）
def BinarySearch(arr, n):
lArr = 0 # 起点位置
rArr = len(arr)-1 # 结束点位置
n = n # 需要查找的数
while lArr <= rArr:
mid = (lArr + rArr) // 2 # 中点位置
if arr(mid) < n: # 如果中点位置的数小于n，则说明在右半部分
lArr = mid + 1
elif arr(mid) > n: # 如果中点位置的数大于n，则说明在左半部分
rArr = mid - 1
else: # 等于则直接输出下标
print(mid)
break
冒泡排序的时间复杂度
def BubbleSort(arr):
for i in range(len(arr)):
for j in range(i,len(arr)):
if arr(i) < arr(j):
arr(i), arr(j) = arr(j), arr(i)
该函数总共执行了：N-1+N-2+N-3+...+1 = N*(N-1)/2 = N²/2-N/2 取最高阶取因数得：O(N²)
所以冒泡排序的时间复杂度为O(N²)
递归算法的时间复杂度
def fac(N):
if N == 0:
return 1
else:
return diGui(N-1) * N
递归函数每次执行调用自己：第一次执行fac(N)，第二次执行fac(N-1)，第三次执行fac(N-2)...最后执行fac(1)，每次执行的是一个常数项，为O(1)
执行次数是N次,所以他的时间复杂度为O(N)
2. 空间复杂度
1. 空间复杂度是算法在执行过程中临死占用存储空间大小的量度，也是一个数学表达式，它的计算是根据变量的个数，和时间复杂度一样使用大O渐进表示法来计算。
冒泡排序的空间复杂度：O(1)
def BubbleSort(arr): for i in range(len(arr)): for j in range(i,len(arr)): if arr(i) < arr(j): arr(i), arr(j) = arr(j), arr(i) 冒泡排序的空间复杂度的算法：在第一次循环的时候创建了i和j两个变量，第二次循环又创建了i和j，所以一个创建了N个i和j，所以他的空间复杂度是O(N)
这种想法的错误的，因为空间复杂度不同于时间，算法在第一次循环时创建了i和j，但是第一次循环结束，i和j被销毁，第二次创建的i和j使用的仍是第一次的空间
他只是创建了两个变量，即常数项用1表示，所以他的空间复杂度为O(1)
递归算法的空间复杂度：O(N)
def fac(N):
if N == 0:
return 1
else:
return diGui(N-1) * N
递归算法的空间复杂度要看栈帧的消耗，即递归的深度，该代码调用了N次，每次都会新建一个栈帧，每个栈帧中有常数项个变量，即O(1)
那么N个栈帧的空间复杂度为O(N)
斐波那契数列的空间复杂度：O(N)
def Fib(N):
if N < 3:
return 1
else:
return Fib(N-1) + Fib(N-2)
当Fib(N)开始递归的时候，会建立N个栈帧，当它递归完了之后，就把它申请的内存归还给操作系统，
然后Fib(N)递归完了，Fib(N-1)才开始递归，它会建立N-1个栈帧，它所申请的内存空间就是之前Fib(N)还给操作系统的那块内存空间，重复利用。
所以他的空间复杂度为O(N)
3. 常见时间复杂度对比
| 函数表达式 | 时间复杂度 | 对应阶 |
| 31415926 | O(1) | 常数项 |
| 3N + 10 | O(N) | 线性阶 |
| 2N² + 5N + 22 | O(N²) | 平方阶 |
| 3log(2)N + 22 | O(logN) | 对数阶 |
| 2N+3Nlog(2)N+14 | O(NlogN) | NlogN阶 |
| n^3+2n^2+4n+6 | O(N³) | 立方阶 |
| 2^n | O(2^N) | 指数阶 |