00｜复杂度分析基础知识

一.简介

1.1 何为“复杂度”

复杂度：指为了执行目标程序，所需要的计算资源与“问题规模”之间的函数关系。

时间复杂度：是指执行当前算法所消耗的时间
空间复杂度：是指执行当前算法需要占用多少内存空间

1.2 问题规模

"问题规模" 是需要根据具体问题来定义的, 通常会用若干个自然数来定义，当然也是根据具体场景和分析侧重来定义的。因此，定义 "问题规模" 本身就是分析过程中的一个很重要的步骤。

1.3 大O符号含义

用大O记法表示的复杂度,叫做渐近复杂度(asymptotic complexity),通常大家说的"分析算法复杂度"指的就是渐近复杂度分析。
引用知乎的一段话：

大O符号是一种算法「复杂度」的「相对」「表示」方式。

相对(relative)：你只能比较相同的事物。你不能把一个做算数乘法的算法和排序整数列表的算法进行比较。但是，比较2个算法所做的算术操作（一个做乘法，一个做加法）将会告诉你一些有意义的东西；

表示(representation)：大O(用它最简单的形式)把算法间的比较简化为了一个单一变量。这个变量的选择基于观察或假设。

二.类型

常见复杂度表示：

O(1): Constant Complexity: Constant 常数复杂度
O(log(n)): Logarithmic Complexity: 对数复杂度
O(n): Linear Complexity: 线性时间复杂度
O(n^2): N square Complexity 平⽅
O(n^3): N square Complexity ⽴⽅
O(2^n): Exponential Growth 指数
O(n!): Factorial 阶乘

2.1 O(1)

# 程序只执行一次
print("hello world")

2.2 O(n)

# 程序线性增长执行
n = 10
for i in range(n):
    print("hello world")

2.3 O(n^2)

# 程序嵌套循环，执行n^2次
n = 10
for i in range(n):
    for j in range(n):
        print("hello world")

2.4 O(log(n))

# 程序步长为2（或者更大），反推其执行次数为log（n）
n = 10
for i in range(0, n, 2):
    print("hello world",i)

2.5 O(k^n)

# pow(n,k)为最终执行的次数，以下为举例
n = 10
k = 3
for i in range(pow(n, k)):
    print("hello world", i)

2.6 O(n!)

# factorial(n)为最终执行的次数，以下为举例
import math
n = 5
for i in range(math.factorial(n)):
    print("hello world", i)

三.小结

以上例子证明了：“print”函数执行多少次，该算法的时间复杂度即为O(x)多少。
借用极客时间的一张图，如下：
复杂度图