算法复杂度

2024年10月18日 | 阅读 24 分钟

算法的空间复杂度和时间复杂度可以用来衡量其有效性。虽然我们大多数人都知道解决编程问题有各种方法，但理解算法如何有效地运行可以为您的编程增添价值。为了确定程序或算法的功效，了解如何通过时间和空间复杂度来评估它们可以帮助程序在特定条件下达到最佳性能。因此，我们成为更高效的程序员。

在接下来的教程中，我们将通过一些例子来讨论算法的复杂度。

那么，让我们开始吧。

理解算法复杂度

算法复杂度是衡量给定输入大小为 n 的算法完成所需时间的一种度量。如果一个算法需要扩展，它应该在有限的实际时间范围内计算输出，即使对于大的 n 值也是如此。出于这个原因，复杂度是根据 n 趋近于无穷大来渐近确定的。虽然复杂度通常是针对时间的，但有时也会根据空间来评估复杂度，以解释算法的内存需求。

当比较算法或寻求改进时，对算法复杂度进行分析是实用的。算法复杂度属于理论计算机科学的一个分支，称为计算复杂度理论。重要的是要指出，我们关注的是算法复杂度的阶，而不是以毫秒为单位的实际执行时间。

算法复杂度也称为复杂度或运行时间。

时间复杂度有什么意义？

首先，让我们了解一下什么定义了算法。

在计算机编程中，算法是一系列有限的、明确定义的指令，通常在计算机中执行，以解决一类问题或执行一项常见活动。根据定义，必须有一系列明确的指令需要提供给计算机来执行算法或执行相同的活动。此外，在可以选择任何可用编程语言的情况下，指令可以采用任何形式的语法和所选编程语言的性能边界。我们还规定算法要在计算机中执行，这会导致在操作系统、处理器、硬件等方面出现后续的偏差，这些也会影响算法的执行方式。

现在我们知道各种因素会影响算法执行的结果，了解这些程序在执行活动时如何高效利用是很明智的。为了评估这一点，我们必须计算算法的空间和时间复杂度。

算法的空间复杂度定义为算法执行所需的空间或内存量，作为输入长度的函数。同时，算法的时间复杂度定义为算法执行所需的时间量，作为输入长度的函数。既然我们知道了时间复杂度的意义，现在是时候理解什么是时间复杂度以及我们如何评估它了。

为了解释，时间复杂度衡量执行算法中每个语句所需的时间。如果一个语句设置为重复运行，那么该语句执行的次数等于 N 乘以该函数每次执行所需的时间。

让我们考虑以下用于在 Python 中打印语句的代码

代码 1

print("This is a simple statement.")<p></p>
<p><strong>Output:</strong></p>
<div class=codeblock3><pre>
This is a simple statement.
</pre></div>
<p><strong>Code 2:</strong></p>
<div class=codeblock><textarea name=code class=xml>
for i in range(10):
   print("This is a simple statement.")

输出

This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.

第一个算法仅定义打印一次语句。执行此算法所需的时间显示为 0 纳秒。第二个算法定义打印相同的语句；但是，这次它设置为在 FOR 循环中执行相同的语句 10 次。在第二个算法中，执行 FOR 循环和 print 语句这两行代码所需的时间是 5 毫秒。此外，随着 N 值的增加，所需时间也会增加，因为该语句将执行 N 次。

注意：上面的代码在 Python-Jupyter Notebook 中执行，操作系统为 Windows 11 64 位 + 处理器 Intel(R) Core(TM) i5-10300H CPU @ 2.50GHz。在不同的硬件、不同的操作系统和不同的编程语言（如果使用）下，上述时间值可能会有所不同。

到目前为止，我们可以得出结论，每当算法使用的语句只执行一次时，它将始终需要相同的时间。那么，当语句处于循环条件时，所需时间会根据循环设置为执行的次数而增加。此外，每当算法包含单次执行语句和循环语句的组合，或者包含嵌套循环语句时，时间都会根据每条语句执行的次数成比例地增加。

既然我们已经理解了时间复杂度的整体概念及其意义，那么现在是时候了解在给定算法中的语句时，如何确定输入与时间之间的关系了。为了定义两者之间的关系，我们将学习大 O 符号。

什么是大 O 符号？

在理论上，大 O 符号用于检查算法的性能/复杂度。
大 O 符号检查算法性能的上限，即最坏情况。
大 O 符号还考虑渐近算法行为，这意味着当输入量变得非常大时方法的性能。
计算复杂度渐近线 O(f) 根据输入数据的量级（CPU 时间、RAM 等）衡量所用资源的阶。

现在，让我们开始探索不同类型的时间复杂度。

有哪些不同类型的时间复杂度？

算法中使用的不同类型的时间复杂度如下所示

常数时间复杂度
线性时间复杂度
对数时间复杂度
二次时间复杂度
三次时间复杂度
指数时间复杂度
准线性时间复杂度
阶乘时间复杂度

以及更多复杂的记法，基于定义函数的类型。

现在让我们详细讨论一些时间复杂度。

常数时间复杂度 - O (1)

当算法不依赖于输入大小 n 时，则称该算法的时间复杂度为常数。这种算法的运行时间不变，与输入大小 n 无关。这种时间复杂度表示为 O(1)。

让我们考虑以下说明相同内容的代码片段。

示例

# defining a function to return the first element of the array
def getFirstElement(list):
    return list[0]

# main function
if __name__ == '__main__':
    # initializing the arrays
    ArrayOne = [10, 12, 34, 4, 16, 23, 69, 13, 8, 22]
    ArrayTwo = [13, 41, 20, 64, 13, 50, 66]

    # calling the function and printing the first element of the array
    print("First Element of the First Array is :", getFirstElement(ArrayOne))
    print("First Element of the Second Array is :", getFirstElement(ArrayTwo))

输出

First Element of the First Array is : 10
First Element of the Second Array is : 13

说明

在上面的代码片段中，我们定义了一个名为 getFirstElement() 的函数，它接受一个列表作为参数。在此函数中，我们返回了列表的第一个数据元素。对于主函数，我们初始化了两个分别包含 10 个元素和 7 个元素的数组，并通过将初始化的数组传递给 getFirstElement() 函数并打印这两个数组的第一个元素来调用该函数。

上面的代码显示，无论数组的长度 (n) 如何，在任何长度的数组中获取第一个元素所需的时间是相同的。如果运行时间被认为是 1 个单位的时间，那么执行数组只需要 1 个单位的时间，与长度无关。因此，该函数属于常数时间，阶为 O(1)。

线性时间复杂度 - O (n)

当算法的运行时间随输入长度线性增加时，则称算法的时间复杂度为线性。这个陈述意味着，每当函数中有一个迭代遍历输入大小为 n 时，算法的时间复杂度将为 O(n) 阶。

让我们考虑以下说明相同内容的代码片段。

示例

# defining a function to print the elements of the array
def printElements(list):
    # using the FOR loop to iterate through the list
    for value in list:
        # printing the elements
        print(value)

# main function
if __name__ == '__main__':
    # initializing the array
    myArray = [10, 12, 34, 4, 16, 23, 69, 13, 8, 22]

    # calling the function and printing all elements of the array
    print("Elements of the Array are : ")
    printElements(myArray)

输出

Elements of the Array are : 
10
12
34
4
16
23
69
13
8
22

说明

在上面的代码片段中，我们定义了一个名为 printElements() 的函数，它接受一个列表作为参数。在此函数中，我们使用了 FOR 循环遍历列表并打印列表的数据元素。对于主函数，我们初始化了一个包含 10 个元素的数组。然后我们打印了一条给用户的消息，并通过将初始化的数组传递给 printElements() 函数来打印数组的元素。

上面的代码显示，运行时间将随数组长度 (n) 线性增加。如果运行时间被认为是 1 个单位的时间，那么执行数组将花费 n 倍的 1 个单位时间。因此，该函数随输入大小线性运行，其阶为 O(n)。

对数时间复杂度 - O (log n)

如果算法在每一步都减小输入数据的大小，则称算法的时间复杂度为对数。这个陈述意味着函数中执行的操作数与输入大小不同。但是，随着输入数据大小的增加，操作数会减少。这种时间复杂度表示为 O(log n)。

具有此类时间复杂度的算法通常在二叉树操作和二分查找函数中找到。此类算法涉及通过将数组分成两半并在一个部分中开始搜索来搜索数组中的给定值。这种方法确保操作不是对列表中的每个数据元素进行。

让我们考虑以下说明相同内容的代码片段。

示例

# defining a function to search a value in data using the binary search
def binarySearch(list, search_value):
    # finding the size of the list using the len() function
    list_size = len(list)
    # initializing the left and right pointers
    left_pointer = 0
    right_pointer = list_size - 1
    
    # using the while loop to iterate through the array from left pointer to right pointer
    while left_pointer <= right_pointer:
        # defining the middle pointer
        middle_pointer = (left_pointer + right_pointer) // 2

        # if the value to be searched is less than the value of the middle pointer, then we will update the right pointer value to the one less than middle pointer 
        if search_value < list[middle_pointer]:
            right_pointer = middle_pointer - 1

        # if the value to be searched is greater than the value of the middle pointer, then we will update the left pointer value to the one more than middle pointer 
        elif search_value > list[middle_pointer]:
            left_pointer = middle_pointer + 1

        # if the value to be searched is equal to the value of the middle pointer, then we will return the middle_pointer 
        else:
            return middle_pointer

    # if the value is not found in the list, we will raise a ValueError saying 'Value is not found in the list.'
    raise ValueError('Value is not found in the list.')

# main function
if __name__ == '__main__':
    # initializing the list
    myArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    # initializing the value to be searched
    value_to_be_searched = 9
    # calling the binarySearch() function and storing the result
    returned_index_value = binarySearch(myArray, value_to_be_searched)

    # printing the result for the users
    print("The index value of", value_to_be_searched, "in", myArray, "=", returned_index_value)

输出

The index value of 9 in [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] = 8

说明

在上面的代码片段中，我们定义了一个名为 binarySearch() 的函数，用于通过二分查找算法在数据中搜索值。此函数将接受两个参数 - 列表和要在列表中搜索的目标值。在此函数中，我们确定了列表的大小，并初始化了两个指针 left_pointer 和 right_pointer。然后我们使用 while 循环从左指针遍历到右指针。在此循环中，我们将中间指针定义为左右指针之间的中间值。然后我们比较目标值是否小于中间值，并将右指针移到中间指针减一的位置。我们还比较目标值是否大于中间值，并将左指针移到中间指针加一的位置。然后我们检查目标值是否等于中间指针，并将中间指针作为目标值的最终索引返回。如果列表中不存在目标值，我们也引发了 ValueError。

上面的代码显示，运行时间将是对数级的，因为在每一步中输入数据的大小都会减小。因此，函数相对于输入数据以对数时间运行，其阶为 O(log n)。

二次时间复杂度 - O (n²)

当算法的运行时间随输入长度非线性 (n^2) 增加时，则称该算法的时间复杂度为非线性或二次。嵌套循环通常属于此阶，其中一个循环需要 O(n)，如果函数包含一个循环内的循环，那么它将是 O(n) * O(n) = O(n^2) 阶。

以类似的方式，如果函数中定义了 'm' 个循环，则阶为 O(n^m)，这被称为多项式时间复杂度函数。

冒泡排序是二次时间复杂度的良好示例，对于列表中的每个值，它都需要将其与列表中的所有其他值进行比较。让我们考虑以下说明同一问题的示例。

示例

# defining a function to sort the list in ascending order using the bubble sort
def bubbleSort(list):
    # defining a flag
    swappedFlag = True
    # using the while loop to iterate through the list
    while swappedFlag:
        # updating the flag value to False
        swappedFlag = False
        # using the for loop to iterate through the list and swapping the positions of the elements to sort them in ascending order
        for i in range(len(list) - 1):
            if list[i] > list[i + 1]:
                list[i], list[i + 1] = list[i + 1], list[i]
                swappedFlag = True

# main function
if __name__ == '__main__':
    # initializing a sample array
    myArray = [12, 21, 17, 16, 14, 18, 15, 13, 42, 10]

    # printing the initial array for the users
    print("The Elements of Array before Sorting :", myArray)
    
    # calling the bubbleSort() function to sort the given array
    bubbleSort(myArray)

    # printing the final sorted array for the users
    print("The Elements of Array after Sorting :", myArray)

输出

The Elements of Array before Sorting : [12, 21, 17, 16, 14, 18, 15, 13, 42, 10]
The Elements of Array after Sorting : [10, 12, 13, 14, 15, 16, 17, 18, 21, 42]

说明

在上面的代码片段中，我们定义了一个名为 bubbleSort() 的函数，它接受一个列表作为参数，使用冒泡排序方法以升序对该列表进行排序。我们在函数内部定义了一个标志，并将其初始设置为 True。然后我们使用 WHILE 循环遍历数组中的元素，直到标志变为 False。在此循环中，我们更新了标志的初始值并将其设置为 False。然后我们再次使用 FOR 循环遍历数组，将当前选定的元素与数组中的其他元素进行比较，如果当前元素大于后一个元素，则交换它们的位置。然后我们将标志设置为 True。对于主函数，我们初始化了要升序排序的数组，并打印给用户。然后我们调用 bubbleSort() 函数，将给定的数组作为其参数，并打印最终数组给用户。

上面的代码显示，运行时间将是二次级的，因为嵌套循环正在运行函数来排序数组的元素。因此，该函数相对于输入数据以二次时间运行，其阶为 O(n^2)。

指数时间复杂度 - O (2ⁿ)

当输入数据的集合每增加一个，增长就翻倍时，则称算法的时间复杂度为指数级。这类时间复杂度通常在蛮力算法中观察到。这种时间复杂度表示为 O(2^n)。

在密码学中，蛮力攻击可以通过迭代子集来系统地检查密码的所有可能数据元素。使用指数算法执行此操作，破解长密码比破解短密码会产生巨大的资源消耗。这是长密码比短密码更安全的原因之一。

指数时间复杂度的例子之一可能是斐波那契数的递归计算。让我们考虑以下说明同一问题的代码片段

示例

# defining a function to return Fibonacci number using recursion
def fibNum(n):
    # returning n if the value of n is less than or equal to 1
    if n <= 1:
        return n
    # recursive call
    return fibNum(n - 1) + fibNum(n - 2)

# main function
if __name__ == '__main__':
    # printing the statement for the users
    print("Fibonacci Series (First Ten Numbers) : ")
    # printing the first ten numbers of Fibonacci series
    for i in range(10):
        print(fibNum(i))

输出

Fibonacci Series (First Ten Numbers) : 
0
1
1
2
3
5
8
13
21
34

说明

在上面的代码片段中，我们定义了一个名为 fibNum() 的函数，它接受 n 作为参数来返回给定位置值的斐波那契数。在此递归函数中，如果 n 的值小于或等于 1，则返回 n。然后我们设置了对函数的递归调用，将斐波那契数列的前两个值相加。对于主函数，我们打印了一条消息，然后使用 FOR 循环调用 fibNum() 函数 i 次来打印前十个斐波那契数。

上面的代码显示，由于我们定义的用于返回斐波那契数的递归函数，运行时间将是指数级的。因此，该函数相对于输入数据以指数时间运行，其阶为 O(2^n)。

准线性时间复杂度 - O (n log n)

如果输入数据中的每个操作都具有对数时间复杂度，则称算法的时间复杂度为准线性。这类时间复杂度通常在用于排序目的的算法中观察到。此类时间复杂度的一些示例算法是归并排序、TimSort、堆排序等等。这种准线性时间复杂度表示为 O(n log n)。

让我们来看一个说明归并排序算法实现的例子，该算法具有准线性时间复杂度

示例

# defining a function to sort the list using the mergesort algorithm
def mergeSort(list):
    # if the list size is less than or equal to 1, return
    if len(list) <= 1:
        return
    
    # defining a middle point of the list
    middlePoint = len(list) // 2

    # separating the list elements to the left and right side of the middle point
    leftData = list[:middlePoint]
    rightData = list[middlePoint:]
    
    # calling the mergeSort() function for left side data and right side data separately
    mergeSort(leftData)
    mergeSort(rightData)
    
    # initializing the left, right and list index
    leftIndex = 0
    rightIndex = 0
    listIndex = 0
    
    # using the WHILE loop to iterate through the list and sort it in ascending order
    while leftIndex < len(leftData) and rightIndex < len(rightData):
        if leftData[leftIndex] < rightData[rightIndex]:
            list[listIndex] = leftData[leftIndex]
            leftIndex += 1
        else:
            list[listIndex] = rightData[rightIndex]
            rightIndex += 1
        listIndex += 1
    
    if leftIndex < len(leftData):
        del list[listIndex:]
        list += leftData[leftIndex:]
    elif rightIndex < len(rightData):
        del list[listIndex:]
        list += rightData[rightIndex:]
    
# main function
if __name__ == '__main__':
    # initializing an unsorted array
    myArray = [29, 11, 7, 16, 52, 38, 33, 23, 14, 40]
    # printing the unsorted array for the users
    print("Unsorted Array :", myArray)
    # calling the mergeSort() function for the given array
    mergeSort(myArray)
    # printing the sorted array as the result for the users
    print("Sorted Array (After Performing Merge Sort) :", myArray)

输出

Unsorted Array : [29, 11, 7, 16, 52, 38, 33, 23, 14, 40]
Sorted Array (After Performing Merge Sort) : [7, 11, 14, 16, 23, 29, 33, 38, 40, 52]

说明

在上面的代码片段中，我们定义了一个名为 mergeSort() 的函数，它接受一个列表作为参数，使用归并排序算法对其进行排序。在此函数中，我们使用 if 条件语句检查列表的大小是否小于或等于 1 并返回。然后我们为列表定义了中间指针，并初始化了两个列表，包含中间指针的左侧和右侧的元素。然后我们调用 mergeSort() 函数两次，并将包含左侧元素和右侧元素的列表传递给它。然后我们初始化了 left、right 和 list 索引为 0，并使用 WHILE 循环遍历列表并相应地对它们进行排序。对于主函数，我们初始化了一个包含十个元素的未排序数组，并打印给用户。然后我们调用 mergeSort() 并将给定的数组作为参数传递。最后，我们为用户打印了结果。

上面的代码显示，运行时间将是准线性的，因为对每个数组的元素进行排序所需的时间是对数级的。因此，该函数相对于输入数据以准线性时间运行，其阶为 O(n log n)。

阶乘时间复杂度 - O (n!)

如果算法的增长方式是基于输入数据的大小以阶乘方式增长，则称算法的时间复杂度为阶乘。例如，

2! = 2 × 1 = 2
3! = 3 × 2 × 1 = 6
4! = 4 × 3 × 2 × 1 = 24
5! = 5 × 4 × 3 × 2 × 1 = 120
6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5,040
8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320
9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 362,880
10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3,628,800

正如我们所观察到的，即使输入的大小很小，上述输入的增长率也非常快。

具有阶乘时间复杂度的算法的一个很好的例子是堆算法，它用于生成 n 个对象的所有可能排列。

堆找到了一种系统的方法，在每一步选择一对数据元素进行交换，以恰好生成这些数据元素的所有可能排列一次。

让我们来看一个说明堆算法实现以生成给定数据的所有可能排列的例子。

示例

# defining a function to implement the heap algorithm
def heapPermutation(list, size):
    # if the size of the list is equal to one
    if size == 1:
        # printing the list and return
        print(list)
        return
    
    # iterating through the size of the list to generate all the possible permutations
    for i in range(size):
        # calling the heapPermutation() function
        heapPermutation(list, size - 1)

        if size % 2 == 0:
            list[i], list[size - 1] = list[size - 1], list[i]
        else:
            list[0], list[size - 1] = list[size - 1], list[0]

# main function
if __name__ == '__main__':
    # initializing the array
    myArray = [1, 2, 3, 4]
    # calling the heapPermutation() function to generate all the possible permutations for the given array

    print("The Possible Permutations of", myArray, "using the Heap Algorithm are as follows:")
    heapPermutation(myArray, len(myArray))

输出

The Possible Permutations of [1, 2, 3, 4] using the Heap Algorithm are as follows:
[1, 2, 3, 4]
[2, 1, 3, 4]
[3, 1, 2, 4]
[1, 3, 2, 4]
[2, 3, 1, 4]
[3, 2, 1, 4]
[4, 2, 3, 1]
[2, 4, 3, 1]
[3, 4, 2, 1]
[4, 3, 2, 1]
[2, 3, 4, 1]
[3, 2, 4, 1]
[4, 1, 3, 2]
[1, 4, 3, 2]
[3, 4, 1, 2]
[4, 3, 1, 2]
[1, 3, 4, 2]
[3, 1, 4, 2]
[4, 1, 2, 3]
[1, 4, 2, 3]
[2, 4, 1, 3]
[4, 2, 1, 3]
[1, 2, 4, 3]
[2, 1, 4, 3]

说明

在上面的代码片段中，我们定义了一个名为 heapPermutation() 的函数，它接受两个参数 - 列表及其大小。在此函数中，我们检查列表的大小是否等于一，并将列表打印给用户。之后，我们遍历列表的大小，并使用堆算法生成所有可能的排列。对于主函数，我们初始化了一个数组并打印了一条消息给用户。然后我们调用 heapPermutation() 函数，并将初始化的数组及其大小作为其参数传递。

请注意，它将根据输入数据的大小以阶乘方式增长。因此，我们可以得出结论，上述算法具有 O(n!) 的阶乘时间复杂度。

如何计算时间复杂度？

我们已经观察到每个函数如何获得阶记法以及运行时间与输入大小操作数之间的关系。现在，是时候根据算法获得的阶记法以及输入大小来理解评估算法时间复杂度的方法，并计算给定 n 时算法执行所需的总运行时间了。

让我们通过一个例子来理解评估算法时间复杂度的方法

给定一个算法，它被定义为

有两个阶为 n 的输入方阵。
两个矩阵中每个数据元素的值都使用 np.random() 方法随机选择。
我们定义了一个与输入矩阵相同阶的零初始化结果矩阵。
矩阵 X 的每个数据元素都乘以矩阵 Y 的每个数据元素，并将结果值存储在结果矩阵中。
然后将结果矩阵转换为列表类型。
将结果列表中的每个数据元素相加，以返回最终答案。

让我们考虑成本函数 C，它是执行函数所花费的每单位时间，而 'n' 表示算法中语句定义的执行次数。

例如，如果执行 PRINT 函数的时间是 1 微秒 (C)，并且算法定义为执行 PRINT 函数 1000 次 (n)，

那么总运行时间 = (C * n) = 1 微秒 * 1000 = 1000 微秒 = 1 毫秒

Line 1 = C1 * 1
Line 2 = C2 * 1
Line 3, 4, 5 = (C3 * 1) + (C3 * 1) + (C3 * 1)
Line 6, 7, 8 = (C4 * [n + 1]) * (C4 * [n + 1]) * (C4 * [n + 1])
Line 9 = C4 * [n]
Line 10 = C5 * 1
Line 11 = C2 * 1
Line 12 = C4 * [n + 1]
Line 13 = C4 * [n]
Line 14 = C2 * 1
Line 15 = C6 * 1

总运行时间 = (C1 * 1) + (C2 * 1) + 3 (C3 * 1) + 3 (C4 * [n + 1]) + (C4 * [n]) + (C5 * 1) + (C2 * 1) + (C4 * [n + 1]) + (C4 * [n]) + (C2 * 1) + (C6 * 1)

我们将所有成本替换为 C，以估计记法的阶。

因此，总运行时间将确定如下

Total run time
= C + 3 C + 3 C + ([n + 1] C * [n + 1] C) + n C + C + [n + 1]C + n C + C
= 7 C + ((n ^ 3) C + 3 (n ^ 2) C + 3n C + C + 3n C + 3 C
= 12 C + (n ^ 3) C + 3 (n ^ 2) C + 6n C
= C (n ^ 3) + C (n ^ 2) + C (n) + C
= O (n ^ 3) + O (n ^ 2) + O (n) + O (1)

通过将所有成本函数替换为 C，我们可以得到输入大小的次数为 3，这表明了该算法时间复杂度的阶。此处，从最终方程可以看出，运行时间与输入大小“n”的多项式函数不同，因为它与输入大小的立方、二次和线性形式相关。

这样，我们就评估了任意给定算法的阶，并估计了当输入大小增加或减小时运行时间的扩展方式。此外，需要注意的是，所有成本值，如 C1、C2、C3、C4 等，都替换为 C 以简化方程并了解记法的阶。在实际中，我们需要知道每个 C 的值，这可以给出给定输入值 'n' 的算法的准确运行时间。

理解算法的最佳情况、最坏情况和平均时间复杂度

让我们考虑一个在无序数据元素列表中按顺序搜索元素的例子。如果我们运气好，元素可能会出现在列表的开头。但是，如果我们运气不好，它可能是列表中的最后一个数据元素。第一种情况称为最佳情况复杂度，而第二种情况称为最坏情况复杂度。如果搜索到的元素始终是列表中的第一个元素，则复杂度将为 O(1)。如果搜索到的元素始终是列表中的最后一个元素，则复杂度将为 O(n)。除了这两种情况，我们还可以计算平均复杂度，它将等于 O(n)。

“复杂度”一词通常指最坏情况复杂度。在数学上，定义了不同的记法如下

最坏情况或上界：大 O：O (n)
最佳情况或下界：大 Omega：Ω (n)
平均情况：大 Theta：Θ (n)
松散上界：小 o：o (n)
松散下界：小 Omega：ω (n)

注意：上述渐近记法的数学表示是线性复杂度的一个例子。

当上界或下界与平均复杂度不一致时，可以将这种复杂度称为非紧边界或松散边界。

还有摊还复杂度，其中复杂度是通过对一系列操作进行平均来计算的。

最常用数据结构中操作的算法复杂度

下表显示了常用数据结构中不同操作的算法复杂度

数据结构	时间复杂度								空间复杂度
	平均数				最坏				最坏
	访问	搜索	插入	删除	访问	搜索	插入	删除
Array	Θ (1)	Θ (n)	Θ (n)	Θ (n)	O (1)	O (n)	O (n)	O (n)	O (n)
Stack	Θ (n)	Θ (n)	Θ (1)	Θ (1)	O (n)	O (n)	O (1)	O (1)	O (n)
Queue	Θ (n)	Θ (n)	Θ (1)	Θ (1)	O (n)	O (n)	O (1)	O (1)	O (n)
单向链表	Θ (n)	Θ (n)	Θ (1)	Θ (1)	O (n)	O (n)	O (1)	O (1)	O (n)
双向链表	Θ (n)	Θ (n)	Θ (1)	Θ (1)	O (n)	O (n)	O (1)	O (1)	O (n)
跳表	Θ (log n)	Θ (log n)	Θ (log n)	Θ (log n)	O (n)	O (n)	O (n)	O (n)	O (n log n)
哈希表	不适用	Θ (1)	Θ (1)	Θ (1)	不适用	O (n)	O (n)	O (n)	O (n)
二叉搜索树	Θ (log n)	Θ (log n)	Θ (log n)	Θ (log n)	O (n)	O (n)	O (n)	O (n)	O (n)
笛卡尔树	不适用	Θ (log n)	Θ (log n)	Θ (log n)	不适用	O (n)	O (n)	O (n)	O (n)
B 树	Θ (log n)	Θ (log n)	Θ (log n)	Θ (log n)	O (log n)	O (log n)	O (log n)	O (log n)	O (n)
红黑树	Θ (log n)	Θ (log n)	Θ (log n)	Θ (log n)	O (log n)	O (log n)	O (log n)	O (log n)	O (n)
伸展树	不适用	Θ (log n)	Θ (log n)	Θ (log n)	不适用	O (log n)	O (log n)	O (log n)	O (n)
AVL 树	Θ (log n)	Θ (log n)	Θ (log n)	Θ (log n)	O (log n)	O (log n)	O (log n)	O (log n)	O (n)
KD 树	Θ (log n)	Θ (log n)	Θ (log n)	Θ (log n)	O (n)	O (n)	O (n)	O (n)	O (n)

一些数组排序算法的算法复杂度

下表显示了不同数组排序算法的算法复杂度

算法	时间复杂度			空间复杂度
	最佳	平均数	最坏	最坏
快速排序	Ω (n log n)	Θ (n log n)	O (n²)	O (log n)
归并排序	Ω (n log n)	Θ (n log n)	O (n log n)	O (n)
TimSort	Ω (n)	Θ (n log n)	O (n log n)	O (n)
堆排序	Ω (n log n)	Θ (n log n)	O (n log n)	O (1)
冒泡排序	Ω (n)	Θ (n²)	O (n²)	O (1)
插入排序	Ω (n)	Θ (n²)	O (n²)	O (1)
选择排序	Ω (n²)	Θ (n²)	O (n²)	O (1)
树排序	Ω (n log n)	Θ (n log n)	O (n²)	O (n)
希尔排序	Ω (n log n)	Θ (n (log n)²)	O (n (log n)²)	O (log n)
桶排序	Ω (n + k)	Θ (n + k)	O (n²)	O (n)
基数排序	Ω (n k)	Θ (n k)	O (n k)	O (n + k)
计数排序	Ω (n + k)	Θ (n + k)	O (n + k)	O (k)
立方排序	Ω (n)	Θ (n log n)	O (n²)	O (n)

下一个主题算法设计技术

我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题

联系信息

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

+91-9599086977

关注我们

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

DAA 教程

渐进分析

复发

排序分析

分而治之

排序

下界理论

线性时间排序

哈希

二叉搜索树

红黑树

动态规划

贪婪算法

回溯

最小生成树

最短路径

所有对最短路径

最大流

排序网络

复杂度理论

近似算法

字符串匹配

面试题

其他

算法复杂度

理解算法复杂度

时间复杂度有什么意义？

注意：上面的代码在 Python-Jupyter Notebook 中执行，操作系统为 Windows 11 64 位 + 处理器 Intel(R) Core(TM) i5-10300H CPU @ 2.50GHz。在不同的硬件、不同的操作系统和不同的编程语言（如果使用）下，上述时间值可能会有所不同。

什么是大 O 符号？

有哪些不同类型的时间复杂度？

常数时间复杂度 - O (1)

线性时间复杂度 - O (n)

对数时间复杂度 - O (log n)

二次时间复杂度 - O (n2)

指数时间复杂度 - O (2n)

准线性时间复杂度 - O (n log n)

阶乘时间复杂度 - O (n!)

如何计算时间复杂度？

理解算法的最佳情况、最坏情况和平均时间复杂度

注意：上述渐近记法的数学表示是线性复杂度的一个例子。

最常用数据结构中操作的算法复杂度

一些数组排序算法的算法复杂度

相关帖子

DAA 算法

算法的需求

DAA 教程

算法设计技术

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器

二次时间复杂度 - O (n²)

指数时间复杂度 - O (2ⁿ)