03 | 如何计算算法的复杂度-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

03 | 如何计算算法的复杂度

在算法的学习与面试过程中，掌握如何计算和分析算法的复杂度是至关重要的。算法复杂度是衡量算法效率高低的一个重要指标，它直接关系到算法在实际应用中的性能表现。本讲将深入探讨如何计算和分析算法的时间复杂度和空间复杂度，帮助读者在算法面试中更加准确地评估算法性能。

一、算法复杂度的基本概念

1.1 时间复杂度

时间复杂度是衡量算法执行时间随输入规模增长而变化的快慢程度。它并不表示算法执行的具体时间，而是描述了一个算法执行时间随输入大小变化的趋势。通常用大O表示法（Big O notation）来表示时间复杂度，记为O(f(n))，其中n是输入规模，f(n)是算法执行时间关于n的某个函数。

1.2 空间复杂度

空间复杂度则关注算法在执行过程中所占用的存储空间大小，包括算法本身所占用的固定空间（如代码、常量等）以及算法在执行过程中临时占用的空间（如变量、数据结构等）。同样，空间复杂度也采用大O表示法来衡量，主要关注的是随着输入规模增长，算法所需额外空间的变化趋势。

二、时间复杂度的计算方法

2.1 基本步骤

确定问题规模：首先明确算法的输入规模n，它可以是数组的长度、图的顶点数等。
找出基本操作：识别出算法中执行次数最多的操作，即算法的核心操作，通常这些操作决定了算法的执行时间。
计算基本操作执行次数：根据输入规模n，用数学表达式表示出基本操作的执行次数。
简化表达式：利用数学方法（如求和、求极限等）对表达式进行化简，直到得到一个关于n的简洁形式。
使用大O表示法：根据化简后的表达式，用大O表示法表示算法的时间复杂度。

2.2 常见时间复杂度分析

常数时间复杂度O(1)：算法的执行时间不随输入规模n的变化而变化，或者虽然变化但可视为常数。
线性时间复杂度O(n)：算法中基本操作的执行次数与输入规模n成正比。
对数时间复杂度O(logn)：常见于二分查找等算法中，基本操作执行次数随着输入规模n的增加而以对数速度增长。
多项式时间复杂度O(n^k)：k为正整数，表示算法的执行时间与n的k次方成正比，复杂度随n的增加而迅速增加。
指数时间复杂度O(2^n)：表示算法的执行时间与2的n次方成正比，这类算法在输入规模稍大时就会变得非常低效。
其他复杂度：如O(nlogn)（如归并排序、快速排序等），O(√n)（如某些特定的查找算法）等。

2.3 实例分析

例1：线性查找

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

该算法中，基本操作是“if arr[i] == x:”这一行，它会在数组中遍历n次（最坏情况下），因此时间复杂度为O(n)。

例2：二分查找

def binary_search(arr, x):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1

二分查找算法中，每次比较都将搜索范围减半，因此基本操作（比较操作）的执行次数为log2(n)（以2为底n的对数），时间复杂度为O(logn)。

三、空间复杂度的计算方法

3.1 基本步骤

识别算法中使用的所有变量和数据结构。
计算每个变量和数据结构所需的空间大小。
累加所有空间需求，并忽略与输入规模无关的常数项。
使用大O表示法表示空间复杂度。

3.2 实例分析

例1：冒泡排序

冒泡排序算法主要通过相邻元素的比较和交换来实现排序，它不需要额外的存储空间（除了几个用于交换的临时变量），因此空间复杂度为O(1)。

例2：归并排序

归并排序算法在排序过程中需要额外的存储空间来存放归并过程中的临时数组，这个数组的大小与输入数组相同，因此空间复杂度为O(n)。

四、复杂度分析的注意事项

忽略低阶项：在计算复杂度时，通常只关注最高阶项，忽略低阶项和常数项。
考虑最坏情况：除非特别说明，一般默认分析的是算法的最坏情况复杂度，因为它提供了算法性能的上限。
避免常见误区：如错误地将循环体内的操作次数视为常数（在循环条件与输入规模相关时），忽略递归调用栈的空间消耗等。

五、总结

掌握算法复杂度的计算方法对于评估算法性能、优化算法设计以及准备算法面试都至关重要。通过理解时间复杂度和空间复杂度的基本概念，掌握计算复杂度的方法和步骤，并结合实例进行实践分析，读者可以更加深入地理解算法复杂度的本质，从而在算法设计和面试中更加游刃有余。希望本讲的内容能为读者在算法学习和面试中提供有力支持。