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

级别： ★☆☆☆☆

标签：「算法」「大O表示法」「算法复杂度」

作者：MrLiuQ

审校：QiShare团队

前一篇介绍了快速排序，本篇将重点介绍“大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
复制代码