时间复杂度

概念定义

根据定义，时间复杂度指输入数据大小为 �N 时，算法运行所需花费的时间。需要注意：

• 统计的是算法的「计算操作数量」，而不是「运行的绝对时间」。计算操作数量和运行绝对时间呈正相关关系，并不相等。算法运行时间受到「编程语言 、计算机处理器速度、运行环境」等多种因素影响。例如，同样的算法使用 Python 或 C++ 实现、使用 CPU 或 GPU 、使用本地 IDE 或力扣平台提交，运行时间都不同。
• 体现的是计算操作随数据大小 �N 变化时的变化情况。假设算法运行总共需要「 11 次操作」、「 100100 次操作」，此两情况的时间复杂度都为常数级 �(1)O(1) ；需要「 �N 次操作」、「 100�100N 次操作」的时间复杂度都为 �(�)O(N) 。

符号表示

根据输入数据的特点，时间复杂度具有「最差」、「平均」、「最佳」三种情况，分别使用 �O , ΘΘ , ΩΩ 三种符号表示。以下借助一个查找算法的示例题目帮助理解。

题目： 输入长度为 �N 的整数数组 nums ，判断此数组中是否有数字 77 ，若有则返回 true ，否则返回 �����false 。

解题算法： 线性查找，即遍历整个数组，遇到 77 则返回 true 。

代码：

• Python
• Java
• C++

 

def find_seven(nums):
    for num in nums:
        if num == 7:
            return True
    return False

• 最佳情况 Ω(1)Ω(1) ： nums = [7, a, b, c, ...] ，即当数组首个数字为 77 时，无论 nums 有多少元素，线性查找的循环次数都为 11 次；
• 最差情况 �(�)O(N) ： nums = [a, b, c, ...] 且 nums 中所有数字都不为 77 ，此时线性查找会遍历整个数组，循环 �N 次；
• 平均情况 ΘΘ ： 需要考虑输入数据的分布情况，计算所有数据情况下的平均时间复杂度；例如本题目，需要考虑数组长度、数组元素的取值范围等；

大 �O 是最常使用的时间复杂度评价渐进符号，下文示例与本 LeetBook 题目解析皆使用 �O 。

常见种类

根据从小到大排列，常见的算法时间复杂度主要有：

�(1)<�(log⁡�)<�(�)<�(�log⁡�)<�(�2)<�(2�)<�(�!)O(1)<O(logN)<O(N)<O(NlogN)<O(N2)<O(2N)<O(N!)

示例解析

对于以下所有示例，设输入数据大小为 �N ，计算操作数量为 �����count 。图中每个「蓝色方块」代表一个单元计算操作。

常数 �(1)O(1) ：

运行次数与 �N 大小呈常数关系，即不随输入数据大小 �N 的变化而变化。

def algorithm(N):
    a = 1
    b = 2
    x = a * b + N
    return 1

对于以下代码，无论 �a 取多大，都与输入数据大小 �N 无关，因此时间复杂度仍为 �(1)O(1) 。

def algorithm(N):
    count = 0
    a = 10000
    for i in range(a):
        count += 1
    return count

线性 �(�)O(N) ：

循环运行次数与 �N 大小呈线性关系，时间复杂度为 �(�)O(N) 。

def algorithm(N):
    count = 0
    for i in range(N):
        count += 1
    return count

对于以下代码，虽然是两层循环，但第二层与 �N 大小无关，因此整体仍与 �N 呈线性关系。

def algorithm(N):
    count = 0
    a = 10000
    for i in range(N):
        for j in range(a):
            count += 1
    return count

平方 �(�2)O(N2) ：

两层循环相互独立，都与 �N 呈线性关系，因此总体与 �N 呈平方关系，时间复杂度为 �(�2)O(N2) 。

def algorithm(N):
    count = 0
    for i in range(N):
        for j in range(N):
            count += 1
    return count

以「冒泡排序」为例，其包含两层独立循环：

1. 第一层复杂度为 �(�)O(N) ；
2. 第二层平均循环次数为 �22N​ ，复杂度为 �(�)O(N) ，推导过程如下：

�(�2)=�(12)�(�)=�(1)�(�)=�(�)O(2N​)=O(21​)O(N)=O(1)O(N)=O(N)

因此，冒泡排序的总体时间复杂度为 �(�2)O(N2) ，代码如下所示。

def bubble_sort(nums):
    N = len(nums)
    for i in range(N - 1):
        for j in range(N - 1 - i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

指数 �(2�)O(2N) ：

生物学科中的 “细胞分裂” 即是指数级增长。初始状态为 11 个细胞，分裂一轮后为 22 个，分裂两轮后为 44 个，……，分裂 �N 轮后有 2�2N 个细胞。

算法中，指数阶常出现于递归，算法原理图与代码如下所示。

def algorithm(N):
    if N <= 0: return 1
    count_1 = algorithm(N - 1)
    count_2 = algorithm(N - 1)
    return count_1 + count_2

阶乘 �(�!)O(N!) ：

阶乘阶对应数学上常见的 “全排列” 。即给定 �N 个互不重复的元素，求其所有可能的排列方案，则方案数量为：

�×(�−1)×(�−2)×⋯×2×1=�!N×(N−1)×(N−2)×⋯×2×1=N!

如下图与代码所示，阶乘常使用递归实现，算法原理：第一层分裂出 �N 个，第二层分裂出 �−1N−1 个，…… ，直至到第 �N 层时终止并回溯。

def algorithm(N):
    if N <= 0: return 1
    count = 0
    for _ in range(N):
        count += algorithm(N - 1)
    return count

对数 �(log⁡�)O(logN) ：

对数阶与指数阶相反，指数阶为 “每轮分裂出两倍的情况” ，而对数阶是 “每轮排除一半的情况” 。对数阶常出现于「二分法」、「分治」等算法中，体现着 “一分为二” 或 “一分为多” 的算法思想。

设循环次数为 �m ，则输入数据大小 �N 与 2�2m 呈线性关系，两边同时取 ���2log2​ 对数，则得到循环次数 �m 与 log⁡2�log2​N 呈线性关系，即时间复杂度为 �(log⁡�)O(logN) 。

def algorithm(N):
    count = 0
    i = N
    while i > 1:
        i = i / 2
        count += 1
    return count

如以下代码所示，对于不同 �a 的取值，循环次数 �m 与 log⁡��loga​N 呈线性关系 ，时间复杂度为 �(log⁡��)O(loga​N) 。而无论底数 �a 取值，时间复杂度都可记作 �(log⁡�)O(logN) ，根据对数换底公式的推导如下：

�(log⁡��)=�(log⁡2�)�(log⁡2�)=�(log⁡�)O(loga​N)=O(log2​a)O(log2​N)​=O(logN)

def algorithm(N):
    count = 0
    i = N
    a = 3
    while i > 1:
        i = i / a
        count += 1
    return count

如下图所示，为二分查找的时间复杂度示意图，每次二分将搜索区间缩小一半。

线性对数 �(�log⁡�)O(NlogN) ：

两层循环相互独立，第一层和第二层时间复杂度分别为 �(log⁡�)O(logN) 和 �(�)O(N) ，则总体时间复杂度为 �(�log⁡�)O(NlogN) ；

def algorithm(N):
    count = 0
    i = N
    while i > 1:
        i = i / 2
        for j in range(N):
            count += 1

线性对数阶常出现于排序算法，例如「快速排序」、「归并排序」、「堆排序」等，其时间复杂度原理如下图所示。

示例题目

以下列举本 LeetBook 中各时间复杂度的对应示例题解，以帮助加深理解。