Part 1.1：什么是算法？什么是复杂度？

🎯 本文目标

通过本文，你将：

✅ 理解算法的本质和核心要素
✅ 掌握时间复杂度和空间复杂度的概念
✅ 学会用大 O 表示法分析算法效率
✅ 建立算法思维的基础框架

1. 什么是算法？

1.1 算法的定义

算法（Algorithm） 是解决特定问题的一系列明确、有限的步骤。

用更通俗的话说：算法就是解决问题的方法和步骤。

🌰 生活中的算法例子

问题：如何煮一碗泡面？

算法步骤：
1. 烧开水
2. 打开泡面包装
3. 将面饼放入碗中
4. 倒入调料包
5. 倒入开水
6. 等待 3 分钟
7. 搅拌均匀
8. 开始享用

这就是一个算法！它具备算法的核心特征。

1.2 算法的五大特征

一个合格的算法必须满足以下五个特征：

特征	说明	例子
有穷性	算法必须在有限步骤内结束	不能无限循环
确定性	每一步都有明确的定义，不能有歧义	“烧开水”而不是”烧水”
输入	算法可以有 0 个或多个输入	煮泡面需要：面饼、水、调料
输出	算法至少有 1 个输出	一碗煮好的泡面
可行性	每一步都可以通过已实现的基本操作执行	不能要求”瞬间移动”

1.3 算法 vs 程序

很多人会混淆”算法”和”程序”，它们的区别是：

算法 = 解决问题的思路（抽象的）
程序 = 算法的具体实现（用编程语言写出来）

举例：

算法：二分查找的思想（每次排除一半数据）
程序：用 Python/Java/C++ 实现二分查找的代码

💡 记住：算法是思想，程序是实现。同一个算法可以用不同语言实现。

2. 为什么要学习算法？

2.1 算法的重要性

在计算机科学中，算法是灵魂，数据结构是骨架。

🔥 算法的三大价值

提升程序效率
- 好的算法可以让程序快 100 倍、1000 倍甚至更多
- 例如：排序 100 万个数，冒泡排序需要几分钟，快速排序只需几秒
解决复杂问题
- 有些问题没有算法根本无法解决
- 例如：导航软件的最短路径、推荐系统的个性化推荐
面试和职业发展
- 大厂面试必考算法（Google、字节、腾讯等）
- 算法能力是程序员核心竞争力之一

2.2 算法学习的误区

❌ 误区 1：算法只在面试时有用
✅ 真相：工程中到处都是算法（缓存淘汰、负载均衡、数据压缩等）

❌ 误区 2：算法就是刷 LeetCode
✅ 真相：刷题是练习，理解原理才是核心

❌ 误区 3：算法太难，学不会
✅ 真相：算法是可以通过系统学习掌握的技能

3. 什么是复杂度？

3.1 为什么需要复杂度分析？

假设你写了两个排序算法，如何判断哪个更好？

方法 1：直接运行测试

import time

start = time.time()
bubble_sort(data)
print(f"冒泡排序耗时：{time.time() - start}秒")

start = time.time()
quick_sort(data)
print(f"快速排序耗时：{time.time() - start}秒")

问题：

❌ 依赖硬件性能（不同电脑结果不同）
❌ 依赖数据规模（数据量小时看不出差异）
❌ 依赖数据特征（有序数据和乱序数据表现不同）

解决方案：复杂度分析

复杂度分析是一种理论分析方法，不依赖具体实现和硬件，只关注算法本身的效率。

3.2 时间复杂度（Time Complexity）

时间复杂度：衡量算法执行时间随数据规模增长的趋势。

📊 核心思想

不关心具体执行了多少秒，只关心执行次数和数据规模 n 的关系。

🌰 例子 1：简单循环

def print_numbers(n):
    for i in range(n):  # 循环 n 次
        print(i)

分析：

循环体执行了 n 次
时间复杂度：**O(n)**（读作”大 O n”）

🌰 例子 2：嵌套循环

def print_pairs(n):
    for i in range(n):      # 外层循环 n 次
        for j in range(n):  # 内层循环 n 次
            print(i, j)

分析：

外层循环 n 次，内层循环 n 次
总执行次数：n × n = n²
时间复杂度：O(n²)

🌰 例子 3：对数复杂度

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

分析：

每次循环，搜索范围减半
执行次数：log₂(n)
时间复杂度：O(log n)

3.3 常见时间复杂度对比

复杂度	名称	例子	n=100 时执行次数
O(1)	常数	数组访问 `arr[0]`	1
O(log n)	对数	二分查找	7
O(n)	线性	遍历数组	100
O(n log n)	线性对数	快速排序、归并排序	700
O(n²)	平方	冒泡排序	10,000
O(n³)	立方	三层嵌套循环	1,000,000
O(2ⁿ)	指数	递归求斐波那契数列	1.27×10³⁰
O(n!)	阶乘	全排列	9.3×10¹⁵⁷

📈 复杂度增长趋势图

时间复杂度增长趋势图
图片来源：Wikipedia

3.4 空间复杂度（Space Complexity）

空间复杂度：衡量算法执行过程中所需额外内存空间随数据规模增长的趋势。

🌰 例子 1：O(1) 空间

def sum_array(arr):
    total = 0  # 只用了一个变量
    for num in arr:
        total += num
    return total

分析：

只使用了固定的几个变量（total）
空间复杂度：O(1)

🌰 例子 2：O(n) 空间

def copy_array(arr):
    new_arr = []
    for num in arr:
        new_arr.append(num)  # 创建了一个新数组
    return new_arr

分析：

创建了一个长度为 n 的新数组
空间复杂度：O(n)

🌰 例子 3：O(n²) 空间

def create_matrix(n):
    matrix = []
    for i in range(n):
        row = [0] * n  # 每行 n 个元素
        matrix.append(row)
    return matrix

分析：

创建了一个 n×n 的二维数组
空间复杂度：O(n²)

4. 大 O 表示法详解

4.1 什么是大 O 表示法？

大 O 表示法（Big O Notation） 是描述算法复杂度的数学符号。

核心规则

只保留最高阶项
- O(n² + n) → O(n²)
- O(n³ + n² + n) → O(n³)
忽略常数系数
- O(2n) → O(n)
- O(3n²) → O(n²)
忽略低阶项
- O(n² + 100n + 1000) → O(n²)

4.2 为什么可以这样简化？

因为我们关心的是增长趋势，而不是精确值。

🌰 例子：n² vs n

当 n = 1000 时：

n² = 1,000,000
100n = 100,000
1000 = 1,000

可以看到，n² 占主导地位，其他项可以忽略。

4.3 最好、最坏、平均情况

算法的复杂度可能因输入数据不同而不同。

🌰 例子：线性查找

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

分析：

最好情况：目标在第一个位置 → O(1)
最坏情况：目标在最后或不存在 → O(n)
平均情况：目标在中间位置 → O(n)

📢 注意：通常我们说的时间复杂度指的是最坏情况。

5. 实战：分析复杂度

5.1 例子 1：简单求和

def sum_n(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

分析：

循环 n 次，每次执行常数时间操作
时间复杂度：O(n)
空间复杂度：O(1)（只用了 total 和 i）

5.2 例子 2：冒泡排序

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]

分析：

外层循环 n 次
内层循环平均 n/2 次
总执行次数：n × (n/2) ≈ n²/2
时间复杂度：O(n²)（忽略系数）
空间复杂度：O(1)（原地排序）

5.3 例子 3：递归求斐波那契数列

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

分析：

每次调用产生 2 个子调用
递归深度为 n
调用次数：2⁰ + 2¹ + 2² + … + 2ⁿ ≈ 2ⁿ
时间复杂度：O(2ⁿ)（指数级，非常慢！）
空间复杂度：O(n)（递归栈深度）

5.4 例子 4：优化后的斐波那契（动态规划）

def fibonacci_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

分析：

循环 n 次，每次常数时间
时间复杂度：O(n)（从 O(2ⁿ) 优化到 O(n)！）
空间复杂度：O(n)（需要数组存储）

6. 复杂度分析的实用技巧

6.1 快速判断技巧

代码特征	时间复杂度
单层循环	O(n)
两层嵌套循环	O(n²)
三层嵌套循环	O(n³)
每次减半（二分）	O(log n)
递归树每层翻倍	O(2ⁿ)
排序 + 循环	O(n log n)

6.2 常见陷阱

❌ 陷阱 1：忽略隐藏的循环

def process(arr):
    for i in range(len(arr)):
        arr.sort()  # sort 本身是 O(n log n)

实际复杂度：O(n² log n)，不是 O(n)！

❌ 陷阱 2：递归的空间复杂度

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

空间复杂度：O(n)（递归栈深度），不是 O(1)！

7. 总结与下一步

7.1 本文核心要点

✅ 算法的本质：解决问题的明确步骤
✅ 时间复杂度：衡量执行时间增长趋势
✅ 空间复杂度：衡量内存使用增长趋势
✅ 大 O 表示法：只保留最高阶项，忽略系数
✅ 常见复杂度：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

7.2 复杂度速查表

操作	最好	平均	最坏
数组访问	O(1)	O(1)	O(1)
数组查找	O(1)	O(n)	O(n)
数组插入	O(1)	O(n)	O(n)
链表访问	O(1)	O(n)	O(n)
链表插入	O(1)	O(1)	O(1)
哈希表查找	O(1)	O(1)	O(n)
二叉搜索树查找	O(log n)	O(log n)	O(n)

7.3 下一步学习

在 Part 1.2：时间复杂度推导方法 中，我们将深入学习：

🔍 如何系统地推导时间复杂度
📐 主定理（Master Theorem）
🌲 递归树分析法
🎯 均摊分析法

8. 练习题

8.1 基础题

题目 1：分析以下代码的时间复杂度

def mystery(n):
    count = 0
    i = 1
    while i < n:
        i = i * 2
        count += 1
    return count

点击查看答案

答案：O(log n)

解析：i 每次乘以 2，从 1 到 n 需要 log₂(n) 次。

题目 2：分析以下代码的时间复杂度

def mystery2(n):
    for i in range(n):
        for j in range(i):
            print(i, j)

点击查看答案

答案：O(n²)

解析：

外层循环 n 次
内层循环次数：0 + 1 + 2 + … + (n-1) = n(n-1)/2 ≈ n²/2
忽略系数，得 O(n²)

8.2 进阶题

题目 3：以下代码的时间复杂度是多少？

def mystery3(n):
    if n <= 1:
        return 1
    return mystery3(n // 2) + mystery3(n // 2)

点击查看答案

答案：O(n)

解析：

递归树深度：log n
每层节点数翻倍，但每个节点处理时间减半
总时间：n × (1 + 1/2 + 1/4 + …) ≈ 2n → O(n)

9. 参考资料

📚 推荐书籍：

《算法导论》（Introduction to Algorithms）
《算法》第 4 版（Algorithms, 4th Edition）
《编程珠玑》（Programming Pearls）

🌐 在线资源：

Big-O Cheat Sheet
VisuAlgo（算法可视化）
LeetCode（算法练习）

📝 写在最后

复杂度分析是算法学习的第一道门槛，也是最重要的基础。

掌握了复杂度分析，你就能：

✅ 快速判断算法的优劣
✅ 在面试中自信地分析算法
✅ 在工程中做出正确的技术选型

记住：算法不是天赋，而是可以通过系统学习掌握的技能。