什么是复杂度？
在程序中，我们所说的复杂度，通常是指一段程序的执行效率和资源消耗，即：时间复杂度和空间复杂度。
时间复杂度：一段代码的执行效率，是对程序时间维度上的时长估算。
空间复杂度：一种数据结构在内存中的资源消耗，是对程序占用的内存大小估算。
什么需要复杂度分析？
通常我们计算一段程序运行的时长和占用内存的大小，是通过统计、监控等方式。
这种程序执行后进行统计的方式，也称之为：事后统计。
事后统计 通常能够得到比较精确得到程序的执行效率分析结果，但是也有一定的局限性。
事后统计的方式，通常复杂，且测试结果对程序运行的环境有较强的依赖性（如硬件的配置高低）。
且无法在程序执行前，预知实现算法的执行效率。
那么，复杂度分析就是对事后统计的一种弥补，弥补了其无法提前对算法评估的能力。
复杂度分析不依赖测试数据，可在程序执行前，就对其算法的执行效率进行初步的分析。
大O复杂度表示法
谈到效率问题，我们首先想到的是，单位时间内发生的频率，更直白的说，就是一个处理一个事物所需时间越短，则效率越高，反之效率就越低。
那么对于程序而言，代码片段的执行效率，就是这段代码的执行所需的时长问题
对于完成相同任务的代码，我们认为，执行完成所需时间越短的代码，效率越高。
那么，怎样不通过事后分析就能得出一段代码的执行效率呢？
先来看一段求和代码：
def nums_sum(nums):
sum = 0
for num in nums:
sum = sum + num
return sum
我们暂且假设，这段代码在CPU执行时，认为每行代码的执行时间是相同的（事实并非如此），那么每行代码的执行时间是 unitTime。
第2行执行了一次，即 1 unitTime，第3、4行是 for 循环的一部分，那么其执行次数是 nums.length，用 n 代替，那么两行的执行时间就是 2n unitTime，因此总执行时间：T(n) = (2n + 1) * unitTime；
可以看到，代码的执行时间 T(n) 跟 代码的执行次数 (2n + 1) 是成正比的，因此我们可以使用大O进行如下表示：
T(n) = O(f(n))
公式中的 f(n) 表示代码执行次数
O 表示执行时间 T(n) 与f(n)表达式成正比。
那么，可以得出 T(n) = O(2n + 1)，再来看一个例子：
def calcFunc():
sum = 0
nums_1 = [1, 2, 3, 4]
nums_2 = [5, 6, 7, 8]
for n_1 in nums_1:
for n_2 in nums_2:
sum = sum + (n_1 * n_2)
return sum
根据第一个例子分析出代码的总时长应该是：T(n) = (2n2 + n + 3) * unitTime = O(2n2 + n + 3)
这就是大 O 时间复杂度表示法。大 O 时间复杂度并不具体表示代码的真正执行时间，而是表示代码执行时间随代码执行次数增长的变化趋势，所以，也叫作渐进时间复杂度。
表达式：T(n) = O(2n2 + n + 3) ，当 n 足够大时（假设无穷大），那么大 O 表达式中，常量 3、低阶 n 和 2n2 的系数 2，对增长趋势的影响可以忽略不计。因此我们只需要记录一个最大量级 n2，那么用大O表示法就是：T(n) = O( n2)，那么示例1就是：T(n) = O(n)
如何进行时间复杂度分析
总的时间复杂度等于量级最大的那段代码的时间复杂度
即只关注代码中的最大量级，比如示例2，代码中存在双重循环，外层循环执行了 n 次，按照乘法法则，内层循环执行了 n2 次，最大量级就是 n2 ，那么它的时间复杂度就是 O( n2 )。同理，示例1中，只有一个循环，因此最大量级是 n，时间复杂度也就是 O(n)。
几种常见的时间复杂度
- 常量阶：O(1)
- 对数阶：O(logn)
- 线性阶：O(n)
- 线性对数阶：O(nlogn)
- 平方阶：O( n2)、立方阶： O(n2)……k次方阶：O(nk)
常量阶O(1)
看到 O(1)，不要误以为是只执行了一行代码，1 只是常量的一种标识，例如，程序中只要不存在循环和递归语句，即使有成千上万行代码，我们也会说它的复杂度是 O(1)，即常量阶
O(logn)、O(nlogn)
先看一段代码：
def calc(n):
i = 1
while i <= n:
i = i * 2
从第四行可以看出，i 从 1 开始，每次循环都会乘以 2。当大于 n 时，循环结束。那么它的计算公式就是这样的
20 21 22 23 …2k …2x = n
因此 2x = n 公式转换为 x = log2 n， 因此这段代码的时间复杂度是 O(log2 n)。
再来看一段代码：
def calc(n):
i = 1
while i <= n:
i = i * 3
根据上面的计算方式，我们可以得到时间复杂度是 O(log3 n)。
那么根据对数公式，我们又可以将 O(log3 n) 转换为 log3 2 * log2 n，因为 log3 2 是一个常量，对增长趋势的影响可以忽略，所以我们可以估算为 O(log2 n) 即：O(logn)
我们已经理解了线性阶复杂度： O(logn)，再来理解线性对数阶 O(nlogn) 就容易了，根据乘法法则，如果一段代码的时间复杂度是 O(logn)， 我们循环执行 n 遍，时间复杂度就变成了O(nlogn)
