## 一.简介 ## 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) ```python # 程序只执行一次 print("hello world") ``` ### 2.2 O(n) ```python # 程序线性增长执行 n = 10 for i in range(n): print("hello world") ``` ### 2.3 O(n^2) ```python # 程序嵌套循环，执行n^2次 n = 10 for i in range(n): for j in range(n): print("hello world") ``` ### 2.4 O(log(n)) ```python # 程序步长为2（或者更大），反推其执行次数为log（n） n = 10 for i in range(0, n, 2): print("hello world",i) ``` ### 2.5 O(k^n) ```python # pow(n,k)为最终执行的次数，以下为举例 n = 10 k = 3 for i in range(pow(n, k)): print("hello world", i) ``` ### 2.6 O(n!) ```python # factorial(n)为最终执行的次数，以下为举例 import math n = 5 for i in range(math.factorial(n)): print("hello world", i) ``` ## 三.小结 以上例子证明了：“print”函数执行多少次，该算法的时间复杂度即为O(x)多少。 借用极客时间的一张图，如下：