算法小专栏：谈谈大O表示法

前一篇介绍了快速排序，本篇将重点介绍“大O表示法”。

阅读本文你将收获：

• 时间复杂度的概念。
• 空间复杂度的概念。
• 大O表示法。

---

一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面来衡量。所对应的两个指标分别是“时间复杂度”与“空间复杂度”。

故在正式介绍大O表示法之前，我们先来看算法优劣的两个指标：“时间复杂度”与“空间复杂度”。

一、时间复杂度

时间复杂度是指一个算法被执行所需要的计算工作量。它用来度量算法执行的时间长短。

时间复杂度常用大O表示法表示，且不包括这个函数的“低阶项”与“首项系数”。

算法的时间复杂度实质上是一个数学函数，它定量描述了该算法的运行时间。常用大O表示法表示。
记做：T(n) = O(f(n))

二、空间复杂度

空间复杂度是指一个算法在运行过程中临时占用存储空间大小的量度。

空间复杂度通常也用大O表示法表示。
记做：S(n)=O(f(n))。

分析一个算法所占用的存储空间大小需要多方面考虑。

比如，
对于递归算法来说，算法本身所占用的存储单元较少，但在运行时需要申请额外的堆栈，从而需要占用较多的临时工作单元。
对于非递归算法来说，算法本身所占用的存储单元较多，而在运行时占用的临时工作单元较少。

三、大O表示法

对于一个算法来说，时间复杂度与空间复杂度往往是互相影响的。追求较好的时间复杂度，往往空间复杂度会差一些。追求较好的空间复杂度，往往时间复杂度会差一些。

算法的时间复杂度和空间复杂度合称为算法的复杂度。而衡量算法复杂度需要用到大O表示法。

3.1 什么是大O表示法？

定义：称一个函数g(n)是O(f(n))，当且仅当存在常数c>0和n0>=1，对一切n>n0均有|g(n)|<=c|f(n)|成立，也称函数g(n)以f(n)为界。记作g(n)=O(f(n))。（来源360百科）

简单来说，大O表示法就是一个由n表示的函数（n代表输入量），通过不断扩大n的值，来渐进反应算法的复杂度。

是不是有点难理解？接下来让我们看几个常见实例就会了然于心。

3.2 大O表示法的几种常见实例

下面从性能的角度，由高到低的介绍几种大O表示法常见实例：

1) 常数级：O(1)

O(1)表示该算法的执行时间（或执行时占用空间）总是为一个常量，不论输入的数据集是大是小。

例如：取数组第一个元素的时间复杂度：

def getFirstElement(arr):
    return arr[0]

2) 对数级：O(log₂n)

O(log₂n)表示每次循环，所要处理的数据量减半。

例如：二分查找的时间复杂度。

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) / 2
        if list[mid] == item:
            return mid
        if list[mid] > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

3) 线性级：O(n)

O(N)表示一个算法的性能会随着输入数据的大小变化而线性变化。

例如：简单查找的时间复杂度。

def easy_search(list, item):
    for index in range(len(list)):
        if list[index] == item:
            return index
    return None

4) 线性对数级：O(nlog₂n)

O(nlog₂n)表示一个算法的性能会随着输入数据的大小变化而线性对数级变化。

例如：快速排序的时间复杂度。

def quickSort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]

        return quickSort(less) + [pivot] + quickSort(greater)

5) 平方级：O(n²)

O(n²)表示一个算法的性能会随着输入数据的大小变化而发生平方级变化。

举例：选择排序的时间复杂度。（典型的两层for循环遍历）

def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

6) 立方级：O(n³)

O(n³)表示一个算法的性能会随着输入数据的大小变化而发生立法级变化。

举例：三层for循环的遍历算法的时间复杂度。

7) k次方级：O(n^k)

O(n^k)表示一个算法的性能会随着输入数据的大小变化而发生k次方级变化。

举例：k层for循环的遍历算法的时间复杂度。

8) 指数级：O(2ⁿ)

O(2ⁿ)表示一个算法的性能将会随着输入数据的每次增加而增大两倍。

举例：斐波那契数列的时间复杂度。

def Fibonacci(n):
    if(n>=2):
        return Fibonacci(n - 1) + Fibonacci(n - 2)
    else:
        return n