算法复杂度是衡量算法效率的重要指标。了解算法的复杂度，有助于我们更好地选择合适的算法解决实际问题。

时间复杂度

时间复杂度是指算法执行时间与输入数据规模之间的关系。通常用大O符号表示，例如O(n)、O(n^2)等。

  • 线性时间复杂度 (O(n)): 算法执行时间与输入数据规模成正比。
  • 对数时间复杂度 (O(log n)): 算法执行时间与输入数据规模的对数成正比。
  • 平方时间复杂度 (O(n^2)): 算法执行时间与输入数据规模的平方成正比。

空间复杂度

空间复杂度是指算法执行过程中所需存储空间的大小。同样使用大O符号表示。

  • 常数空间复杂度 (O(1)): 算法执行过程中所需存储空间不随输入数据规模变化。
  • 线性空间复杂度 (O(n)): 算法执行过程中所需存储空间与输入数据规模成正比。

例子

以下是一个线性时间复杂度的例子：

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

以下是一个对数时间复杂度的例子：

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

更多关于算法复杂度的内容，可以参考算法复杂度详解。

Algorithms