当前位置：首页 > article >正文

【漫话机器学习系列】017.大O算法（Big-O Notation）

article 2024/12/24 1:01:18

大 O 表示法（Big-O Notation）

大 O 表示法是一种用于描述算法复杂性的数学符号，主要用于衡量算法的效率，特别是随着输入规模增大时算法的运行时间或占用空间的增长趋势。

基本概念

时间复杂度
- 描述算法所需的运行时间如何随输入数据规模 n 增大而增长。
- 表示形式：如 $eq?O%281%29$ , $eq?O%28n%29$ , $eq?O%28n%5E2%29$ , $eq?O%28%5Clog%20n%29$ 。
空间复杂度
- 描述算法所需的内存空间如何随输入数据规模 n 增大而增长。
- 表示形式：与时间复杂度类似，常见为 $eq?O%281%29$ , $eq?O%28n%29$ 等。
渐进性描述
- 大 O 表示法不关注常数因子，只关注随着输入规模无限增长时的增长趋势。例如，若运行时间为 $eq?T%28n%29%20%3D%203n%5E2%20+%202n%20+%201$ ，其渐进复杂度为 $eq?O%28n%5E2%29$ 。

常见的时间复杂度

以下列举了一些常见的时间复杂度，从快到慢排序：

常数时间 $eq?O%281%29$
- 算法的运行时间与输入规模无关。
- 示例：数组索引访问、变量赋值。
```
def constant_example(arr):
    return arr[0]  # 只访问一次，无论数组多大
```

对数时间 $eq?O%28%5Clog%20n%29$

每次操作将问题规模缩小（如二分查找）。
示例：二分查找。

def binary_search(arr, target):
    low, high = 0, 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

线性时间 $eq?O%28n%29$

算法需要逐个处理输入的每个元素。
示例：线性搜索。

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

线性对数时间 $eq?O%28n%20%5Clog%20n%29$

通常出现在排序算法（如归并排序、快速排序）。

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):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

平方时间 $eq?O%28n%5E2%29$

通常出现在嵌套循环中（如冒泡排序）。
示例：冒泡排序。

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]

指数时间 $eq?O%282%5En%29$

通常出现在递归问题中（如穷举所有子集）。
示例：斐波那契数列递归计算。

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

阶乘时间 $eq?O%28n%21%29$
- 通常出现在全排列问题中，增长极快。
- 示例：旅行商问题暴力求解。

大 O 表示法的特性

忽略低阶项
- 复杂度表示只关注增长最快的项。例如，若 $eq?T%28n%29%20%3D%203n%5E2%20+%202n%20+%201$ ，则复杂度为 $eq?O%28n%5E2%29$ 。
忽略常数因子
- 只关注输入规模的增长趋势。例如，若 $eq?T%28n%29%20%3D%205n$ ，则复杂度为 $eq?O%28n%29$ ，忽略常数 5。
渐进上界
- 大 O 表示的是最坏情况下的增长速度，是算法复杂度的上界。