摘要： ...

算法复杂度分析面试题，一文给你讲透！

算法复杂度分析的重要性

在程序员面试中，算法复杂度分析可是个高频考点。为啥它这么重要呢？因为它能衡量一个算法的效率。想象一下，同样解决一个问题，有的算法运行起来快如闪电，有的却像蜗牛爬，这其中的差别就在复杂度上。像在开发大数据处理程序时，高效的算法能节省大量时间和资源，所以面试官特看重候选人对复杂度分析的掌握。

时间复杂度分析

常见时间复杂度类型

1. O(1)：这是最理想的情况，叫常数时间复杂度。不管数据规模怎么变，算法执行时间都差不多。比如从数组里按索引取一个元素，不管数组有多大，时间基本固定，就像伸手从口袋里拿指定位置的东西，一下就拿到了。
2. O(n)：线性时间复杂度。算法执行时间和数据规模成正比。比如说遍历一个数组，数组里元素越多，花费时间就越长，就像排队点名，人越多花的时间越多。
3. O(n²)：平方时间复杂度。一般出现在嵌套循环里，像冒泡排序，每轮比较次数随着数据规模增大急剧上升，整体时间复杂度就是 O(n²)，相当于一群人两两握手，人数越多，握手次数大幅增加。
4. O(log n)：对数时间复杂度。随着数据规模增大，算法执行时间增长很慢。二分查找就是典型，每次查找都把范围缩小一半，就像猜数字，每次都能排除一半可能性，查找次数和数据规模的对数相关。

分析步骤

1. 确定基本操作：就是算法里最核心、执行次数最多的操作。比如排序算法里的比较操作，搜索算法里的查找操作。
2. 计算执行次数：看看基本操作在不同数据规模下执行多少次。比如一个简单循环从 1 到 n，基本操作执行 n 次。
3. 确定时间复杂度：把执行次数用大 O 表示法简化。像执行 n 次就是 O(n)，如果是 2n + 3 次，去掉常数项和系数，也是 O(n)，因为数据规模很大时，常数和系数影响不大。

空间复杂度分析

常见空间复杂度类型

1. O(1)：算法执行过程中占用的空间固定，不随数据规模变化。比如简单的算术运算，不管操作数多大，用的额外空间就那么多。
2. O(n)：占用空间和数据规模成正比。像创建一个大小为 n 的数组，就需要 O(n) 的空间，就像建一排大小一样的房子，房子数量越多，占地越大。
3. O(n²)：比如创建一个 n×n 的二维数组，空间复杂度就是 O(n²)，类似建一个方阵的房子，边长增加，占地面积大幅增加。

分析要点

1. 考虑额外空间：主要看算法运行时除输入数据外，额外占用的空间。像排序时如果创建了临时数组，这部分空间就得算进去。
2. 递归算法的空间：递归调用会占用栈空间，每次调用都有开销。递归深度是 n 的话，空间复杂度可能就是 O(n)，因为栈空间随着递归深度增加。

面试题实战

例题 1：计算数组元素之和

def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

1. 时间复杂度：基本操作是 total += num，循环执行 n 次（n 是数组长度），所以时间复杂度是 O(n)。
2. 空间复杂度：除了输入数组，只用到一个变量 total，额外空间固定，所以空间复杂度是 O(1)。

例题 2：冒泡排序

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]
    return arr

1. 时间复杂度：外层循环 n 次，内层循环最多 n - 1 次，整体是 O(n²)。
2. 空间复杂度：除输入数组，只用到几个临时变量，空间复杂度是 O(1)。

总之，掌握算法复杂度分析，多做练习题，面试遇到这类题就能轻松拿下，向理想工作更进一步！