数据结构与算法-时间，空间复杂度分析
如何去评判一个数据结构或者算法的好坏
如何去评判一个数据结构或者算法的好坏呢？那无非是运行的快不快，耗不耗内存。所以执行效率和内存消耗都是考量算法的指标？那我们如何去评估执行效率和内存消耗呢？
下面有几个代码案例，哪组的运行时间最短？
def printInfo():
print("hello world")
def printInfo_2(n):
for i in range(n):
print("hello world")
def printInfo_3(n):
for i in range(n):
for j in range(n):
print("hello world")
几乎可以毋庸置疑地说出我们调用printInfo()方法，运行时间是最短的，也可以说运行效率最高。那运行的时间就能代表运行效率吗？其实这里存在一些问题。
-
运行结果依赖运行环境
运行环境硬件的不同对运行结果很造成很大的影响，我们执行相同的代码，如果一个
Intel Core i9处理器和在Intel Core i3处理器上运行，不用说，一定是i9的执行速度比在i3上的执行速度要快。不仅是处理器，还有内存，机械硬盘和固态硬盘，网络，流量等等方面都会对运行结果造成影响。 -
运行结果依赖问题规模
例如上面的例子，如果说我们调用
printInfo_2()和printInfo_3()这两个函数，传入的参数都是1，那么和直接调用printInfo()方法执行的时间就是一样的。因为数据规模一样，都是1。不同问题规模也是会影响运行的结构。
所以，我们就需要一个不用具体的运行数据，甚至不需要运行代码，就可以粗略的计算出算法的执行效率的方法，那这就是我们需要说的时间，空间复杂度。
时间复杂度
什么是时间复杂度？
什么是时间复杂度？别急，在下定义之前，我们可以类比一下生活中一些估算时间的案例。
| 动作 | 预估时间 |
|---|---|
| 呼吸 | 几毫秒 |
| 戴口罩 | 几秒 |
| 烧开水 | 几分钟 |
| 上班 | 几小时（正常8小时，万一加班呢？） |
| 开发一个功能需求 | 几天 |
| 开发一个管理系统 | 几个月 |
| 开发大型系统 | 几年 |
可以发现，我们在生活中预估时间的时候，都是带着几和一个单位，这个几就是表示了一个大概的数目。那时间复杂度我们也可以参照类似的方法，去预估算法的运行效率。
时间复杂度是对一个算法运行时间长短的量度，仅仅表示代码执行时间随数据规模增长的变化趋势，也叫做渐进时间复杂度，用O表示。
比如O(1)，O(n^2)
常见的时间复杂度
n表示问题规模，复杂度从小到大排序
-
Constant(常量级) Time: O(1)
-
Logarithmic(对数级) Time: O(log(n))
-
Linear(线性级) Time: O(n)
-
Linearithmic(线性对数级) Time: O(nlogn)
-
Quadratic(平方级) Time: O(n^2)
-
Cubic(立方级) Time: O(n^3)
-
Exponential（指数级) Time: O(b^n), b > 1
-
Factorial（阶乘级) Time: O(n!)
如何计算时间复杂度
def cal():
n = 100
m = 1000
return sum = n + m
如果调用cal() 那是不是O(3)?
答案：一般我们都会忽略系数和常数项，所以，如果调用cal() 的时间复杂度就是O(1)。
def loop():
for i in range(10):
print("hello world")
答案：时间复杂度还是O(1)，为什么？就算是循环，数据规模是固定的，就只会循环十次，所以时间复杂度是O(10 * 1)，由于10是系数，1是单位，所以忽略系数，时间复杂度还是O(1)。
def loop(n):
for i in range(0, n, 2):
print("hello world")
答案：时间复杂度是O(n)，每次i的值加2，所以一共会执行f(n)=n/2次，时间复杂度是O(f(n))，忽略系数，时间复杂度是O(n)。
def cal_2(n):
for i in range(n):
print("hello world")
for j in range(n):
print("hello world")
答案：时间复杂度是O(n^2)，首先一共会执行f(n) = n * (1 + n)= n ^ 2 + n次，所以时间复杂度是O(f(n))，我们一般会取最高项，所以时间复杂度是O(n^2)
# O(logn): 对数时间复杂度
i = 1
while(i <= n){
print(i)
i *= 2
}
答案：时间复杂度是O(logn), f(n) = log2 n，忽略底数，时间复杂度是o(logn)
def loop(n):
for i in range(n):
print("hello world")
for j in range(3 * n):
print("hello world")
for i in range(2 * n):
print("hello world")
答案：数学公式f(n) = n * (3n + 2n) = 3n^2 + 2n^2 = 5n^2，时间复杂度为O(5n^2)，忽略系数，所以时间复杂度是O(n^2)
def loop(n):
for i in range(n):
print("hello world")
for j in range(3 * n):
print("hello world")
for m in range(10):
print("hello world")
for x in range(n*n):
print("hello world")
答案：数学公式f(n) = n * (3n + 10 + n^2) = n^3 + 3n^2 + 10n，时间复杂度为O(n^3 + 3n^2 + 10n)，忽略系数，取最高项,所以时间复杂度是O(n^3)
def fib(n){
if n <= 2:
return n
return fib(n - 1) + fib(n - 2);
答案：O(2^n) ，数学公式f(n) = f(n - 1) + f(n - 2),需要使用数学归纳法。
def permutations(ls, start, end):
if(start >= end):
print(ls)
else:
for i in range(start, end + 1):
ls[start], ls[i] = ls[i], ls[start]
permutations(ls, start + 1, end)
ls[start], ls[i] = ls[i], ls[start]
答案：O(n!)
def cal(int m, int n):
sum_1 = 0
for i in range(m):
sum_1 += i
sum_2 = 0
for j in range(n):
sum_2 += i
return sum_1 + sum_2
答案：O(m + n)
时间复杂度的分析方法
- 一般我们都会忽略系数，常数项，底数。
- 只关注循环执行次数最多的一段代码，其实就是取次数最高项。
- 如果问题规模是n，折半操作了就是
logn系列的，m层嵌套循环就是n^k。 - 加法法则：总时间复杂度等于量级最大的那段代码的时间复杂度，同级的循环是相加关系。
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，不同级的循环是相乘关系。
注意
在分析时间复杂度的时候，还有需要在分析一下这个算法的最好，最坏时间复杂度。
- 最好时间复杂度：在最理想的情况下，该算法运行的时间复杂度
- 最坏时间复杂度：在最糟糕的情况下，该算法运行的时间复杂度
例如，排序算法，例如冒泡排序，最好情况时间复杂度就是O(1)，这是在完全有序的情况下，即为最理想的情况。最坏时间复杂度是O(n^2)，这是在完全逆序的情况下[5,4,3,2,1]需要排序成[1,2,3,4,5]，这就是最糟糕的情况。尤其是最坏时间复杂度，也是参考的算法好坏的一个重要指标。
空间复杂度
空间复杂度是对一个算法在运行时临时占用存储空间大小的量度。也是渐进式的
常见的O(1),O(n),O(n^2)
！！重要的思想：空间换时间（升维），提高运行效率。想想map-reduce，这种分布式架构的计算架构，就是把一个复杂的问题，分配到不同的机器上处理，提高计算效率。
