算法的时间复杂度与渐近表示法

算法的复杂度是衡量在给定规模（n）的输入下，算法所需时间和/或空间的度量。算法的复杂度确实会受一些特定因素影响，例如：计算机体系结构（即硬件平台）、抽象数据类型（ADT）的表示、编译器效率、底层算法的复杂度、输入规模。其中最关键的因素通常是底层算法的复杂度以及输入规模。

在 DataCamp 的博客 Python 数据结构教程中，您可以了解数据结构的基础概览以及其在 Python 中的实现。该博文介绍了 Python 的基本数据结构，并带您了解抽象数据类型与数据结构、原始数据结构与非原始数据结构。

渐近分析

渐近分析是指用计算中的数学单位来衡量任意代码或操作的运行时间。其操作以函数形式（如 f(n)）来度量。在数学分析中，渐近分析（asymptotics）是一种描述极限行为的方法。

算法所需时间可分为三类：最坏情况——算法所需的最大时间，分析算法时最常用；最好情况——算法或代码片段所需的最小时间，分析时通常不单独计算；平均情况——算法或代码片段的平均所需时间，分析时有时会考虑。

渐近表示法

常用来计算算法运行时间复杂度的表示法如下：

Big O 表示法
Big θ 表示法
Big Ω 表示法

Big Oh 表示法，Ο

Big O 用于度量算法的性能或复杂度。从更数学的角度看，它是函数增长率的上界：如果函数 g(x) 的增长不快于函数 f(x)，则称 g 属于 O(f)。一般来说，它用于表示算法的上界，衡量最坏时间复杂度，即算法可能完成所需的最长时间。

Big Omega 表示法，Ω

Ω(n) 表示法用来形式化表达算法运行时间的下界。它衡量最好情况的时间复杂度，即算法可能完成所需的最短时间。

Big Theta 表示法，θ

θ(n) 表示法用来形式化表达算法运行时间的上下界同时受限。

用于判定各类算法复杂度的表示法

Big O 表示法使用最为广泛，主要用于求算法的上界；而 Big θ 表示法有时用于刻画平均情况；在三者中，Ω 表示法使用最少。

下面您将看到在算法中使用这些表示法来判定特定算法复杂度的示例。

以快速排序为例：

快速排序是一种分治（Divide and Conquer）算法，用于排序。它是一种系统地将元素置于有序位置的方法，例如将数组中的元素按升序或降序排列。该算法会从给定数组中选择一个枢轴（pivot）或索引。枢轴可有不同的选择方式。下面的示例实现选择最后一个元素作为枢轴。

快速排序的核心在于分区。先从数组中选取一个分区元素，然后将该分区元素（例如 pit）放在正确位置，所有大于分区元素的放在其右侧，小于分区元素的放在其左侧。

#The last element will be taken as a pivot by the use of the function
#The smaller element is placed left to the pivot
#The greater element is placed to the right of the pivot
def partition(array,low,high):
    i = ( low-1 )         # index of smaller element is chosen
    pivot = array[high]     # pivot is chosen

    for j in range(low , high):

        #Is the element less or equal to the pivot
        if   array[j] <= pivot:

            # increment index of smaller element
            i = i+1
            array[i],array[j] = array[j],array[i]

    array[i+1],array[high] = array[high],array[i+1]
    return ( i+1 )

# The main crux of the problem that implements Quick sort is
#array[] is to be sorted
#high is the ending index
#low is the starting index

# Function to do Quick sort
def quickSort(array,low,high):
    if low < high:

       #pit is the partitioning index
        pit = partition(array,low,high)

      #Element sorted before and after partition
        quickSort(array, low, pit-1)
        quickSort(array, pit+1, high)

array=[2,4,6,8,10,12]
n = len(array)
quickSort(array,0,n-1)
print ("The Sorted array is:")
for i in range(n):
    print ("%d" %array[i]),
技术支持

已排序的数组为：
2
4
6
8
10
12
您将得到如下输出：

已排序的数组为：2 4 6 8 10 12

现在是分析时间复杂度的时候了。首先：

最好情况：Ω(n log(n))
平均情况：Θ(n log(n))
最坏情况：O(n^2)

现在，我们来分析上述代码。

最好情况：当分区元素每次都能选到中间位置作为枢轴时。由于算法会在前一半和后一半上递归调用，因此——所需的总步骤数等于每步将问题规模除以 2，从 n 递减到 1 所需的次数。也就是 n/2/2/2/.../2=1，进行了 k 次。注意该等式实际为：n / 2^k = 1。由于 2^log n = n，可得 k = log n。因此算法所需的步骤（迭代）数为 O(log n)，而每次迭代为 O(n)，合起来为 O(n log n)。

平均情况：要做平均情况分析，需要考虑数组的所有排列并计算每个排列所需时间。可参考归并排序。

最坏情况：在最坏情况下，如果每次选择第一个元素为枢轴，而输入序列本身是升序或降序，则会出现最坏复杂度。原因在于分区后，一边的规模为 1，另一边为 n-1。此时，T(n) 表示函数：对 n 个元素快速排序的时间 T(n) = 分区 n 个元素所需时间 O(n) + 对 n-1 个元素快速排序的时间 T(n-1)。所以，T(n) = T(n-1) + O(n) => T(n) = O(n^2)。

示例

下面的代码未必花哨，您也许不会称其为算法，但技术上讲，任何能完成某件事的代码都是一种算法，即解决特定问题的方法。上面的算法示例是一个包含单条打印语句的 for 循环。

print('I love Python');
技术支持

Hello world!
上述算法的时间复杂度为 O(1)，因为它总是只需一步。这是常数时间。

stuffs= ['eggs','toothbrush','kittens','mugs']
for stuff in stuffs:
    print("Here's a stuff: {}".format(stuff));
技术支持

Here's a stuff: eggs Here's a stuff: toothbrush Here's a stuff: kittens Here's a stuff: mugs 您会如何用 Big O 表示法描述上述算法的效率？

要分析上述算法，需要考虑该算法要执行多少步。在上面的例子中，列表里有四个元素，您需要各打印一次。但如果列表中不止 4 个元素，比如有 15 个，for 循环对 15 个元素也会执行同样数量的步骤吗？由于这个 for 循环执行的步骤数与元素数量相同，您应当说该算法的效率是 O(N) 而不是 O(1)。

下一个示例是一个用于判断一个数是否为素数的简单 Python 算法：

def is_prime(number):   
    for i in range(2, number):       
        if number % 2 == 0:           
            return True   
    return False
技术支持

上述代码接受一个数字作为参数，然后开始一个 for 循环，将该数分别除以从 2 到该数之间的每个数，检查是否有余数。如果没有余数，说明该数不是素数，并立即返回 False。如果一直到该数为止都存在余数，则说明该数是素数，返回 True。

您可以判定上述算法的效率为 O(N)。该示例并未以数组或列表形式接收数据，而是以传入的数字作为参数。如果传入一个任意数字，例如 11，for 循环大约运行 11 步（实际上是 9 步，因为从 2 开始，到该数之前结束）。对于数字 101，循环大约运行 101 步。由于步骤数随传入函数的数字线性增长，这是 O(N) 的典型示例。

def twoForLoops(n):
    for i in range(1,n):
        print("Printing:"+i);
    for i in range(1,100):
        print("Printing:"+i);
技术支持

在上述代码中，算法的复杂度为 O(N)。由于第二个循环的参数是 100，可以忽略不计，因为表达复杂度时需要假设 N 很大。

def twoConditionalLoops(m,n):
    for i in range(0,m):
        print("Printing:"+i);
    for i in range(0,n):
        print("Printing:"+i);
技术支持

这里有两个循环，一个长度为 m，另一个长度为 n。同样需要假设 m 和 n 都很大，则操作的复杂度为 O(n+m)。由于两个循环彼此独立并接收不同的输入，复杂度呈加性。

def twoNestedForLoops(int m,int n):
    for i in range(0,n):
        for j in range(0,m):
            print("Printing:"+(i*j));
技术支持

这里是嵌套的 for 循环，同样假设 n 和 m 很大，则操作的复杂度为 O(n*m)。由于循环相同且为嵌套结构，复杂度呈乘性。

恭喜！

您已经读完本教程！过程中，您学习了渐近表示法，以及程序员与数据科学家常用的一项基础工具。您刚刚学到了一种用浅显语言分析复杂度的基本且易懂的方法，没有引入过多术语与严格的数学推导。尽管数据结构与算法常被认为是计算机科学或相关专业的课程内容，非专家也同样有必要了解这一主题。想要更深入学习，您可以参考此链接：MIT 开放式课程算法课

如果您想进一步学习 Python，请查看这些 DataCamp 课程：

主题

Python 数据分析

主题

技术

用 Python 分析代码复杂度

使用 AI 探索