01：复杂度：如何衡量程序运行时的效率

写在前面

在python语言中，并没有直接使用数组这个概念，而是使用列表(list)和元祖(tuple)这两种集合，他们本质上都是对数组的封装。后文中提到的数组概念，对应的是python语言的中的列表(list)。

一、复杂度的定义

复杂度是一个关于输入数据量n的函数 。假设你的代码的复杂度是f(n)，那么就用大写字母O和括号，把f(n)括起来就可以了，即O(f(n))。例如，O(n)表示的是，复杂度与计算实例的个数n线性相关；O(logn)表示的是，复杂度与计算实例的个数n对数相关。
通常复杂度的计算方法遵循以下几个原则：

• 首先，复杂度与具体的常系数无关，例如O(n)和O(2n)表示的是同样的复杂度。我们详细分析一下，O(2n)=O(n+n)=O(n)+O(n),也就是说，一段O(n)复杂度的代码是先后执行两遍O(n),其复杂度是一致的。
• 其次，多项式级的复杂度相加的时候，选择最高项作为结果，例如O(n²)+O(n)和O(n)表示的是同样的复杂度。因为O(n²)+O(n)=O(n²+n)。随着n越来越大，二阶多项式的变化率是比一阶多项式更大的，因此可以省略一阶多项式。
• 最后，O(1)页表示一个特殊复杂度，含义为某个任务通过有限可数的资源即可完成。此处有限可数的具体含义是：与输入数据量n无关

1. 例题:对于输入的数组，输出与之逆序的数组。例如，输入 a=[1,2,3,4,5]，输出[5,4,3,2,1]

• 方法一：建立并初始化数组b，得到一个与输入输入数组等长的全零数组。通过一个for循环，从左到右将a数组的元素，从右到左地赋值到b数组中，最后输出数组b得到结果。
  代码如下：

#!/usr/bin/python
# -*- coding: utf-8 -*-
def void_s1_1():
    a = [1,2,3,4,5]
    b = list()
    for index,value in enumerate(a):
        b.append(a[len(a)-index-1])
    print(b)
if __name__ == "__main__":
    void_s1_1()

这段代码的输入数据是a，数据量就等于数组a的长度。代码中有一个for循环，作用是给数组b赋值，其执行次数与数据量相等，因此，代码的时间复杂度就是O(n)。
空间方面的主要体现在计算过程中，对于存储资源的消耗情况。上面代码我们定义了一个新的数组b，它与输入的数组a的长度相等。因此，空间复杂度就是O(n)。

• 方法二：定义一个缓存变量tmp，接着通过一个for循环，从0遍历到a数组长度的一半(即len(a)/2)。每次遍历就是交换收尾对相应的元素。最后打印数组a，得到结果。

#!/usr/bin/python
# -*- coding: UTF-8 -*-
def void_s1_2():
    a = [1,2,3,4,5]
    for index in range(len(a)/2):
        tmp = a[index]
        a[index] = a[len(a)-index-1]
        a[len(a)-index-1] = tmp
    print(a)
        
if __name__=="__main__":
    void_s1_2()

这段代码包含了一个for循环，执行的次数是数组长度的一半，时间复杂度变成了O(n/2)。根据复杂度与具体的常系数无关的性质，这段代码的时间复杂度也就是O(n)。
空间方面，我们定义了一个tmp变量，它与数组长度无关。也就是，输入是5个元素的数组，需要一个tmp变量；输入是50个元素的数组，依然需要一个tmp变量。因此，空间复杂度与输入数组长度无关，即O(1)。

二、时间复杂度与代码结构的关系

• 例1，定义一个数组a = [1,4,3],查找数组a中的最大值，代码如下：

#!/usr/bin/python
# -*- coding: UTF-8 -*-
def void_s1_3():
    a = [1,4,3]
    max_val = a[1]
    for value in a:
        if value > max_val:
            max_val = value
    print(max_val)
        
if __name__=="__main__":
    void_s1_3()

这个简单的例子实现方法就是，暂存当前最大值并把所有元素遍历一遍即可。因为代码结构上需要使用一个for循环，对数组虽有元素处理一遍，所以时间复杂度为O(n)。

• 例2，定义一个数组a=[1,3,4,3,4,1,3],查找数组中出现次数最多的那个数字

#!/usr/bin/python
# _*_coding:utf-8 _*_
def void_s1_4():
    a = [1, 3, 4, 3, 4, 1, 3]
    val_max = -1
    time_max = 0
    for i in range(len(a)):
        time_tmp = 0
        for j in range(len(a)):
            if a[i] == a[j]:
                time_tmp = time_tmp + 1
            if time_tmp > time_max:
                time_max = time_tmp
                val_max = a[i]
    print(val_max, time_max)
if __name__ == "__main__":
    void_s1_4()

这段代码，采用了双层循环的方式进行计算：第一层循环，我们对数组中的每个元素进行遍历；第二层循环，对于每个元素计算出现的次数，并且通过当前元素次数time_tmp和全局最大次数变量time_max的大小关系，持续保存出现次数最多的那个元素及其出现次数。由于是双层循环，这段代码在时间方面消耗就是n*n的复杂度，也就是O(n²)

• 经验性结论：

1.一个顺序结构的代码，时间复杂度是O(1)。
2.二分查找，或者更通用地说是采用分而治之的二分策略，时间复杂度都是O(logn)。
3.一个简单的for循环，时间复杂度是O(n)。
4.两个顺序执行的for循环，时间复杂度是O(n)+O(n)=O(2n)，其实也是O(n)。
5.两个嵌套的for循环，时间复杂度是O(n²)

小结

• 什么是时间复杂度
  时间复杂度是对一个算法运行时间的长短的量度，用大O表示，记做T(n)=O(f(n))。常见的时间复杂度按照从低到高的顺序，包括O(1)、O(logn)、O(n)、O(nlogn)、O(n²)
• 什么是空间复杂度
  空间复杂度是对一个算法在运行的过程中占用存储空间大小的量度，用大O表示，记作S(n)=O(f(n))。常见的空间复杂度按照从低到高的顺序，包括O(1)、O(n)、O(n²)等。其中递归算法的空间复杂度和递归深度成正比。
• 推导复杂度的原则
  1.与具体的常系数无关，O(n)和O(2n)表示同样的复杂度
  2.复杂度相加的时候，选择最高阶作为结果，也就是说O(n²)和O(n²)+O(n)表示的是同样的复杂度。
  3.O(1)也是表示一个特殊的复杂度，即任务与算例个数n无关。