每日一问之算法的时间复杂度

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 3.5k | 阅读时长 ≈ 3 分钟

写在前面

这周调整了下计划，鉴于很多不懂的知识需要大量的时间去消化及整理输出，因此，改为每逢节假日更新每日一问。

今天来整理算法复杂度的相关知识。在算法中包含两种复杂度，一种是时间复杂度，另一种是空间复杂度。这篇文章主要总结 时间复杂度 相关的知识点。

  • 时间复杂度
  • 大 O 表示法
  • 计算时间复杂度

时间复杂度

  • 时间频度
    在计算机中，不可能真正的去计算算法的每条语句的执行时间，只有真正上机测试才能知道大概时间。但是实际工作中，不可能把所有的算法都运行测试一遍，这不现实也浪费时间。我们只需要知道算法中主要部分的运行时间就可以了。我们都知道一个算法的运行时间与算法中语句的执行次数成正比，所以**将一个算法中的语句的执行次数称为语句频度或时间频度，记为 T(n)**。n 为问题的规模，时间频度会随着 n 的变化而变化。

  • 时间复杂度
    在计算机科学中，时间复杂度（Time Complexity）是一个定性描述运行算法所花费的时间的度量。**常用大 O 表示法来度量时间复杂度，记为 T(n) = O(f(n))**。

    在时间频度 T(n) 中，n 又代表着问题的规模，当 n 不断变化时，T(n) 也会不断地随之变化。为了了解这个变化的规律，时间复杂度这一概念就被引入了。一般情况下算法基础操作的重复执行次数为问题规模 n 的某个函数，也就是时间频度 T(n)。如果有某个辅助函数 f(n)，当趋于无穷大的时候，T(n)/f(n) 的极限值是不为零的某个常数，那么 f(n) 是 T(n) 的同数量级函数，记作 T(n)=O(f(n))，被称为算法的渐进时间复杂度，又简称为时间复杂度。- 算法（一）时间复杂度[1]

大 O 表示法

在计算机科学领域，会用大 O 符号或者说大 O 表示法来度量一个算法的时间复杂度。那什么是大 O 表示法呢？

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others collectively called Bachmann–Landau notation or asymptotic notation.
大 O 表示法是一种数学符号，用于描述当参数趋向于特定值或无穷大时函数的限制行为。它是 Paul Bachmann，Edmund Landau 等人发明的一系列符号的之一，统称为巴赫曼 - 兰道符号或渐近符号。- 维基百科[4]

因为时间复杂度为 T(n)=O(f(n))，有个趋近函数 O()，所以被称为大 O 表示法。现在假设一个列表包含 n 个元素。我们用简单查找的话，需要遍历检查每一个元素，因此需要执行 n 次操作。使用大 O 表示法，其运行时间为 O(n)，f(n) = n 为操作数。这里需要注意的是，大 O 表示法是没有单位的，它指的并不是以秒为单位的运行时间。大 O 表示法能够用来比较操作数，通常它指的是算法运行时间的增速。比如，为检查长度为 8 的列表，用简单查找法的时间复杂度是 O(f(n))，f(n) = 8；如果用二分查找的话，时间复杂度是 O(f(n))，f(n) = log2 8 = 3。从计算结果上看来，几乎快了 3 倍。

还有一点需要注意的是，大 O 表示法描述的始终是最坏的情况。

常见的一些大 O 运行时间有以下几种：

  • O(1)：常数时间，如哈希表
  • O(n)：线性时间，如简单查找
  • O(log2n)：对数时间，如二分查找
  • O(nlog2n)：如快速排序
  • O(n2)：如选择排序
  • O(n!)：阶乘时间，这是一种非常慢的算法

计算时间复杂度

知道了大 O 表示法，那么实际的时间复杂度要怎么计算呢？下面举几个例子来说明。

**O(1)**：描述了一个算法不管输入的大小是多少，其时间复杂度永远为常数（不变）。比如，下方的例子，判断一个字符串 list 的首个元素是否为空。因为无论输入的 list 有多长，都只判断首字符是否为空，执行次数为 1，所以时间复杂度为 O(1)。

1
2
def isFirstElementNull(str_list):
        rerurn str_list[0] == ''

**O(n)**：描述了一个算法的时间复杂度将随着算法输入的增加而线性增加。比如，下面的算法，判断一个字符串 list 是否包含某些子字符串值。虽然算法可能会很早的就停止循环，并不完全执行所有的迭代，但需记得大 O 表示法描述的是最坏的情况。如果一个算法最大迭代 n 次，那么其时间复杂度就是 O(n)。所以，下面函数的时间复杂度为 O(n)。

1
2
3
4
5
6
7
def isContainValue(str_list, value):

    for i in str_list:
        if i == value:
            return True
        else:
            return False

**O(n2)**：描述了一种算法，其时间复杂度与输入数据集的大小的平方成正比。这在涉及数据集的嵌套迭代的算法中很常见。更深的嵌套迭代将会有 O(n3)，O(n4) 等。比如，下面的代码是两层迭代，按照最坏的打算，迭代总次数为 ixj，是两个数的相乘，可以直接表示为 nxn，即 n 的平方。所以，时间复杂度可以表示为 O(n2)。

1
2
3
4
5
6
def isContainDuplicates(str_list):
    for i in range(len(str_list)): # 最多迭代 i 次
        for j in range(len(str_list): # 最多迭代 j 次
            if i != j and str_list[i] = str_list[j]:
                return True
    return False

**O(log2n)**：描述的是一种二分查找的时间复杂度。二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回 null 。比如，要猜测 1-100 中的一个数字。二分查找将每次迭代的数据集减半，直到找到该值，或者直到它不再分割数据集为止。 迭代中的数据集大小依次有 n，n/2，n/4，….，n/2k（k 为循环的次数）。因为最后结果 n/2k >= 1。如果令 n/2k = 1，将得到 k = log2n。所以，二分查找的时间复杂度为 O(log2n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def binary_search(list, item):
    
    low = 0 
    high = len(list) - 1
    
    while low <= high :
        mid = (low + high) % 2 
        guess = list[mid]
        
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1 
        else:
            low = mid + 1 
    
    return None

参考

[1]. 算法（一）时间复杂度

[2]. 算法图解 - Aditya Bhargava

[3]. A beginner’s guide to Big O notation

[4]. Big O notation - wikipedia

[5]. Binary Search - 二分查找

P.S：文中有错欢迎指出，互相学习。