编辑“︁时间复杂度”︁（章节）

== 常见时间复杂度类型 ==
以下是程序员必须掌握的几种典型时间复杂度（按效率从高到低排序）：

=== 常数时间 O(1) ===
算法执行时间与输入规模无关。例如访问数组元素：
<syntaxhighlight lang="python">
def get_first_element(arr):
    return arr[0]  # 无论arr多大，操作次数固定
</syntaxhighlight>

=== 对数时间 O(log n) ===
常见于二分查找等分治算法。每次操作将问题规模减半：
<syntaxhighlight lang="python">
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
</syntaxhighlight>

=== 线性时间 O(n) ===
执行时间与输入规模成正比。例如遍历数组：
<syntaxhighlight lang="python">
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1
</syntaxhighlight>

=== 线性对数时间 O(n log n) ===
高效排序算法（如归并排序、快速排序）的典型复杂度：
<syntaxhighlight lang="python">
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)  # merge操作时间复杂度为O(n)
</syntaxhighlight>

=== 平方时间 O(n²) ===
常见于嵌套循环，如冒泡排序：
<syntaxhighlight lang="python">
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]
</syntaxhighlight>

=== 指数时间 O(2ⁿ) ===
穷举算法（如解决汉诺塔问题）的典型特征，性能随输入规模急剧下降。