编辑“︁算法复杂度分析”︁（章节）

== 算法复杂度分析 ==

'''算法复杂度分析'''是计算机科学中评估算法效率的核心方法，主要研究算法在不同输入规模下消耗的'''时间'''和'''空间'''资源。通过复杂度分析，开发者可以预测算法在大规模数据下的性能表现，并为优化提供理论依据。

=== 基本概念 ===

==== 时间复杂度 ====
描述算法运行时间随输入规模增长的变化趋势，用'''大O符号'''（Big O notation）表示，常见类型包括：
* <math>O(1)</math>：常数时间（如数组索引访问）
* <math>O(\log n)</math>：对数时间（如二分查找）
* <math>O(n)</math>：线性时间（如遍历数组）
* <math>O(n^2)</math>：平方时间（如冒泡排序）

==== 空间复杂度 ====
描述算法执行过程中所需的额外存储空间随输入规模的变化趋势，同样使用大O符号表示。

=== 大O符号的数学定义 ===
若存在正常数 <math>c</math> 和 <math>n_0</math>，使得对所有 <math>n \geq n_0</math>，有：
<math>f(n) \leq c \cdot g(n)</math>
则记作 <math>f(n) = O(g(n))</math>。

=== 常见复杂度对比 ===
<mermaid>
gantt
    title 时间复杂度增长趋势
    dateFormat  X
    axisFormat %s
    section 复杂度
    O(1)         :a1, 0, 1
    O(log n)     :a2, 0, 3
    O(n)         :a3, 0, 10
    O(n log n)   :a4, 0, 30
    O(n²)        :a5, 0, 100
</mermaid>

=== 代码示例分析 ===

==== 示例1：常数时间 <math>O(1)</math> ====
<syntaxhighlight lang="python">
def get_first_element(arr):
    return arr[0]  # 无论数组多大，操作耗时相同
</syntaxhighlight>

==== 示例2：线性时间 <math>O(n)</math> ====
<syntaxhighlight lang="python">
def find_max(arr):
    max_val = arr[0]
    for num in arr:  # 遍历所有元素
        if num > max_val:
            max_val = num
    return max_val
</syntaxhighlight>

==== 示例3：平方时间 <math>O(n^2)</math> ====
<syntaxhighlight lang="python">
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):          # 外层循环
        for j in range(n-i-1):  # 内层循环
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
</syntaxhighlight>

=== 实际案例分析 ===

'''案例：数据库索引优化'''
* 问题：无索引时查询需<math>O(n)</math>时间扫描全表
* 解决方案：使用B树索引将查询优化至<math>O(\log n)</math>
* 效果：当数据量从10<sup>6</sup>增至10<sup>9</sup>时：
** 线性搜索：耗时增加1000倍
** 二分搜索：耗时仅增加3倍（因<math>\log_2(10^9) \approx 30</math>）

=== 递归算法的复杂度 ===
递归复杂度通常使用'''主定理'''（Master Theorem）分析。对于形式 <math>T(n) = aT(n/b) + f(n)</math>：
* 若 <math>f(n) = O(n^{\log_b a - \epsilon})</math>，则 <math>T(n) = \Theta(n^{\log_b a})</math>
* 若 <math>f(n) = \Theta(n^{\log_b a})</math>，则 <math>T(n) = \Theta(n^{\log_b a} \log n)</math>

=== 复杂度分析的局限性 ===
1. 忽略常数因子：<math>1000n</math>和<math>0.01n^2</math>在小数据量时后者更快
2. 不考虑硬件特性（如缓存局部性）
3. 最坏情况分析可能过于悲观（如快速排序平均<math>O(n \log n)</math>）

=== 练习题目 ===
1. 分析以下函数的时间复杂度：
<syntaxhighlight lang="python">
def mystery_function(n):
    count = 0
    for i in range(n):
        for j in range(i, n):
            count += 1
    return count
</syntaxhighlight>
（答案：<math>O(n^2)</math>）

=== 进阶技巧 ===
* '''摊还分析'''：适用于动态数组扩容等场景
* '''空间-时间权衡'''：如哈希表通过增加空间降低查询时间
* '''输入敏感分析'''：如插入排序在近似有序数据中表现优异

通过系统学习算法复杂度分析，开发者可以：
- 合理选择算法解决特定问题
- 预估系统处理大规模数据的能力
- 在面试中准确分析代码性能

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:算法基础]]