理解时间复杂度，附带示例

可以理解的是，在选择算法时，性能是最重要的因素之一。如果使用的算法效率低下，无论代码的其余部分如何优化，性能都会不佳。衡量算法性能的主要方法是使用一种称为时间复杂度的概念。这个概念起初可能看起来很复杂，所以我们将详细解释它是什么，如何表示它，以及常见复杂性的示例。

什么是时间复杂度？

简单来说，时间复杂度是一种表示算法运行时间随输入规模增加而增加的方式。通常，输入规模对算法的性能有很大影响。例如，当在数组中查找特定元素时，复杂度通常等于o(n)。这意味着它在n上线性地依赖，n是输入的大小。随着元素数量的增加，我们必须搜索更多的元素才能找到我们想要的元素。因此，算法的运行时间更长。

应该说，尽管渐进符号是一个紧密相关的概念，但它与时间复杂度不同。可以将渐进符号视为表示时间复杂度的方式，而时间复杂度是其基本概念。考虑我们以前的例子，o(n)被认为是渐进符号，用于表示搜索算法的时间复杂度。接下来我们将介绍时间复杂度的类型以及如何使用渐进符号表示它们。

影响时间复杂度的因素有哪些？

如前所述，影响时间复杂度的主要因素之一是输入规模。然而，这并不是唯一的因素。执行的操作数量也极大地影响复杂性，嵌套循环的存在，递归，甚至我们使用的硬件也会影响复杂性。

时间复杂度的常见情况及示例

有许多不同的时间复杂度可能，每个时间复杂度都有自己独特的符号表示法。大o符号通常用于表示复杂性随输入规模增长的方式。您可能经常遇到的符号包括o(1)，o(n)，o(log n)，o(n log n)，o(n²)，o(n³)，o(2ⁿ)和o(n!)。接下来我们将详细介绍这些符号。

常数时间 – o(1)

这种复杂度被称为常数时间，因为它与输入规模无关。因此，无论输入是什么，运行时间都不会改变。以下是一些o(1)出现的例子：

• 检查一个整数是奇数还是偶数。
• 检查一个项目是否为空。
• 访问某种数据结构中特定索引处的元素。

例如，考虑下面这段python代码：

def access_element(arr, index):
    return arr[index]

在这里，我们试图访问“arr”数组中“index”索引的元素。由于索引即使添加更多元素也不会改变，所以在这里所需的时间是恒定的。

线性时间 – o(n)

另一种常见的复杂度类型是线性时间，或o(n)。这根据输入规模成比例地增加。这主要出现在以下情况中：

• 获取数组的最小或最大值。
• 对每个元素执行某个操作。
• 打印列表中的所有值。

例如，我们有下面这个操作：

def sum_elements(arr):
    total = 0
    for element in arr:
        total += element
    return total

在这里，我们将数组中元素的值相加。由于我们对每个元素执行相同的操作，所以随着列表中元素的增加，复杂度也会增加。

对数时间 – o(log n)

当我们说对数时间时，通常意味着速度每次操作都会减半。例如，二分搜索算法。该算法通过获取一个排序的列表和一个目标元素，然后将搜索区域反复减半，将目标与中间元素进行比较来工作。由于列表是排序的，根据中间元素的大小，我们可以确定目标是否在左半部分还是右半部分。然后，该算法重复这些步骤以在对数时间内找到目标。在python中可以这样使用：

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

arr = [2, 5, 8, 12, 16, 23, 38]
target = 16

index = binary_search(arr, target)
if index != -1:
    print("element", target, "found at index", index)
else:
    print("element", target, "not found in the list.")

在这个例子中，我们正在寻找值为16的元素，它在索引4处找到。二分搜索的时间复杂度是对数时间，但等于2log(n)。因此，在3次操作后找到目标，因为以2为底的log(7)约等于3。可以在下面的图片中看到这一点。

用python说明对数时间。

©jingzhengli.com

线性对数时间 – o(n log n)

与对数时间类似，线性对数时间还具有与输入大小相关的额外依赖性。 归并排序是这种算法的一个很好的例子。它通过分治过程工作，类似于二分搜索，但在所有子数组完全分割后执行合并过程。考虑下面的代码：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    merged = []
    i = 0
    j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    merged.extend(left[i:])
    merged.extend(right[j:])

    return merged

arr = [8, 3, 1, 7, 4, 6, 2, 5]
sorted_arr = merge_sort(arr)
print(sorted_arr)

我们有一个包含8个元素的数组，它被分割成越来越小的一半，直到无法再分割为止。然后合并这些数组以给出一个排序好的数组，如图所示。

归并排序用于说明线性对数时间。

©jingzhengli.com

二次时间 – o(n²)

二次时间是多项式时间的一种形式（o(n^c），其中复杂度随着输入大小呈指数倍增长。我们可以将冒泡排序算法视为这种时间复杂度的例子，其中相邻的元素不断交换，直到排序完成。在以下代码中展示了这一点。

def bubble_sort(arr):
    n = len(arr)

    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                
arr = [8, 3, 1, 7, 4, 6, 2, 5]
bubble_sort(arr)
print(arr)

在最坏的情况下，我们必须交换每个元素，所以操作的次数呈平方级增长。

冒泡排序算法是平方时间的一个很好的例子。

©jingzhengli.com

立方时间 – o(n³)

立方时间意味着复杂度的增长甚至比平方时间更快。因此，我们通常希望在可以的情况下避免更高的多项式复杂度。一个例子是用于计算图中最短路径距离的弗洛伊德-沃尔什算法。下面是示例代码：

def floyd_warshall(graph):
    n = len(graph)
    distances = graph.copy()

    for k in range(n):
        for i in range(n):
            for j in range(n):
                distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])

    return distances

inf = float('inf')
graph = [
    [0, inf, -2, inf],
    [4, 0, 3, inf],
    [inf, inf, 0, 2],
    [inf, -1, inf, 0]
]

shortest_paths = floyd_warshall(graph)
for row in shortest_paths:
    print(row)

由于我们必须使用3个嵌套的for循环来迭代每对顶点和潜在的较短路径，复杂度是立方级的。这是因为每个循环都依赖于输入大小，并且必须完成所有迭代。值得注意的是，弗洛伊德-沃尔什实际上是一个立方级时间算法的相当快的例子，只要它用于一个相当典型的图。

用程序说明立方级时间。

©jingzhengli.com

指数时间 – o(2ⁿ)

这里的指数意味着随着输入的增加，操作的数量会翻倍。我们可以用递归的斐波那契过程来说明：

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

result = fibonacci(5)
print(result)

这个简单的例子计算第5个斐波那契数。输出结果是5。由此可见，指数操作对于大型数据集来说是不可用的，因为复杂度增长非常快。

用于生成斐波那契数的程序用于说明指数时间。

©jingzhengli.com

阶乘时间 – o(n!)

一个数的阶乘是它之前的所有整数的乘积，再加上自身。例如，3的阶乘等于6，因为1 * 2 * 3 = 6。由于这种复杂度的增长非常大，阶乘算法在日常编程中很少使用。然而，生成字符串中所有排列或单个值的可能组合是一个阶乘时间的例子。例如，考虑以下代码：

def generate_permutations(elements):
    if len(elements) == 1:
        return [elements]

    permutations = []
    for i in range(len(elements)):
        remaining = elements[:i] + elements[i+1:]
        sub_permutations = generate_permutations(remaining)
        for perm in sub_permutations:
            permutations.append([elements[i]] + perm)

    return permutations

elements = [1, 2, 3]
permutations = generate_permutations(elements)
for perm in permutations:
    print(perm)

在这个例子中，我们试图找到元素[1, 2, 3]的所有可能的排列。递归地，每个元素都被选择为起始元素，并计算排列。在这里，我们得到了6个排列，因为有3个元素。结果可以在图片中看到。

用程序演示的阶乘时间。

©jingzhengli.com

时间复杂度的影响和应用

理解算法的时间复杂度对于最大化算法的效率和可扩展性至关重要。可以预期，时间复杂度较低的算法更高效且更易于扩展。能够确定速率决定的算法或最慢的算法有助于识别我们过程中的瓶颈并优化这些步骤。因此，时间复杂度在设计算法和优化性能方面非常重要，并在软件工程、数据库系统、机器学习和计算科学等领域应用广泛。

总结

时间复杂度与渐进符号密切相关，渐进符号用于表示时间复杂度。最常见的时间复杂度类型包括o(1)、o(n)、o(n^c)、o(log n)和o(n log n)。选择适合您需求的正确算法，并优化其性能，对于使代码高效且可扩展至关重要。了解时间复杂度的影响将帮助您设计具有更好性能的程序，并减少在大量数据上执行操作所需的时间。