Python 算法基础篇之什么是算法

1. 算法是什么？一个生活化的理解

1.1 从"做西红柿炒蛋"说起

想象你要教一个完全不会做饭的人做西红柿炒蛋，你会怎么写步骤？

步骤1：准备2个西红柿，洗净切块 步骤2：打3个鸡蛋，加盐搅拌均匀 步骤3：热锅倒油，油热后倒入蛋液 步骤4：蛋液凝固后盛出备用 步骤5：锅中再倒少许油，放入西红柿翻炒 步骤6：西红柿出汁后倒入炒好的鸡蛋 步骤7：加盐调味，翻炒均匀后出锅

这就是算法！一系列明确的、有限的、可执行的步骤，用于解决特定问题（做出一道菜）。

1.2 算法的正式定义

算法（Algorithm）：解决特定问题的一系列清晰指令，满足以下特性：

• 有穷性：必须在有限步骤内结束
• 确定性：每条指令含义明确，无歧义
• 可行性：每条指令都可以通过基本操作实现
• 输入：零个或多个输入
• 输出：至少一个输出

# 算法 vs 程序# 算法是"思想"，程序是"实现"# 算法：找出列表中的最大值# 思路：假设第一个最大，逐个比较更新# 程序：Python 实现deffind_max(arr):ifnotarr:returnNonemax_val=arr[0]# 假设第一个最大fornuminarr[1:]:# 逐个比较ifnum>max_val:max_val=num# 更新最大值returnmax_val# 测试numbers=[3,1,4,1,5,9,2,6]print(f"最大值是：{find_max(numbers)}")# 9

1.3 算法无处不在

🎯核心认知：算法不是程序员的专属，它是解决问题的通用方法论。学算法，就是学如何高效思考。

2. 算法与程序：灵魂与躯壳

2.1 同一个算法，多种实现

问题：计算 1 + 2 + 3 + … + 100

算法一：逐个累加（循环）

defsum_naive(n):"""逐个相加"""total=0foriinrange(1,n+1):total+=ireturntotalprint(sum_naive(100))# 5050

算法二：高斯求和公式（数学）

defsum_gauss(n):"""高斯算法：n * (n + 1) / 2"""returnn*(n+1)//2print(sum_gauss(100))# 5050

算法三：递归

defsum_recursive(n):"""递归：sum(n) = n + sum(n-1)"""ifn==1:return1returnn+sum_recursive(n-1)print(sum_recursive(100))# 5050

对比：

💡启示：算法决定效率的上限，程序决定实现的质量。高斯公式这个算法本身，就比逐个累加快无数倍——这是算法层面的碾压。

2.2 算法的层次

┌─────────────────────────────────────────┐ │ 第4层：数学算法（最优） │ │ 如：高斯求和、矩阵快速幂 │ ├─────────────────────────────────────────┤ │ 第3层：高级数据结构算法 │ │ 如：平衡树、图算法、动态规划 │ ├─────────────────────────────────────────┤ │ 第2层：基础算法 │ │ 如：排序、搜索、递归、分治 │ ├─────────────────────────────────────────┤ │ 第1层：暴力枚举 │ │ 如：逐个尝试所有可能 │ └─────────────────────────────────────────┘

3. 为什么算法如此重要？

3.1 场景一：从"能用"到"好用"

假设你在开发一个用户搜索功能：

方案A：暴力搜索

defsearch_users(users,keyword):"""在用户列表中搜索，暴力匹配"""results=[]foruserinusers:ifkeywordinuser['name']orkeywordinuser['email']:results.append(user)returnresults# 1000个用户：0.1秒 ✓# 100万个用户：100秒 ✗ 用户已经关闭页面了

方案B：使用索引（算法优化）

fromcollectionsimportdefaultdictclassUserSearchEngine:def__init__(self):self.index=defaultdict(set)# 倒排索引defadd_user(self,user):"""建立索引"""words=user['name'].lower().split()words+=user['email'].lower().split('@')forwordinwords:self.index[word].add(user['id'])defsearch(self,keyword):"""基于索引搜索"""keyword=keyword.lower()returnself.index.get(keyword,set())# 100万个用户：0.001秒 ✓✓✓# 性能提升 10万倍！

🚀这就是算法的威力：同样的功能，不同的算法，用户体验天差地别。

3.2 场景二：资源有限时的生存法则

真实案例：NASA 的火星探测器

约束条件： - 处理器：200MHz（比你的手机慢50倍） - 内存：256MB - 通信延迟：4~24分钟（地球到火星） - 电量：太阳能，有限 没有优秀算法 = 任务失败

3.3 场景三：面试与职业发展的硬通货

国内大厂面试算法题占比： ┌─────────────────┬─────────────┐ │ 公司 │ 算法题占比 │ ├─────────────────┼─────────────┤ │ 字节跳动 │ 70% │ │ 阿里巴巴 │ 60% │ │ 腾讯 │ 55% │ │ 美团 │ 65% │ │ Google │ 75% │ │ Meta │ 70% │ └─────────────────┴─────────────┘ 为什么？因为算法能力是"可迁移的智力"。

3.4 算法重要性的四个维度

效率 ↑ 快 ←──┼──→ 省 (时间) │ (空间) ↓ 正确 第5维度：可维护性（代码可读、可扩展）

4. 如何衡量算法的好坏？

4.1 不是"跑得快"这么简单

importtimedeftest_performance():"""同一算法在不同数据下的表现"""# 算法：冒泡排序defbubble_sort(arr):n=len(arr)foriinrange(n):forjinrange(0,n-i-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]returnarr# 测试不同规模forsizein[100,1000,5000]:arr=list(range(size,0,-1))# 最坏情况：逆序start=time.time()bubble_sort(arr.copy())elapsed=time.time()-startprint(f"规模{size:5d}:{elapsed:.4f}秒")test_performance()

典型输出：

规模 100: 0.0012秒 规模 1000: 0.0891秒 规模 5000: 2.3124秒 ← 规模×5，时间×26！

⚠️问题：运行时间受硬件、语言、当前系统负载影响，不能作为衡量标准。

4.2 正确的衡量方式：复杂度分析

我们需要一种与机器无关的衡量方式，关注算法本身的效率随数据规模增长的变化趋势。

5. 算法复杂度：Big O 表示法

5.1 什么是 Big O？

Big O 表示法：描述算法运行时间（或空间）随输入规模增长的变化趋势。

核心思想：当 n → ∞ 时，只保留增长最快的项，忽略常数和低阶项。

精确计算：T(n) = 3n² + 5n + 100 Big O： O(n²) ← 只保留最高阶 为什么可以忽略？ 当 n = 100万时： 3n² = 3,000,000,000,000 5n = 5,000,000 100 = 100 5n + 100 相对于 3n² 可以忽略不计

5.2 常见复杂度对比

可视化增长曲线：

操作次数 ↑ │ 1e30 ┤ ★ 2ⁿ │ ★ 1e20 ┤ ★ │ ★ 1e9 ┤ ★ │ ★ ▲ n³ 1e6 ┤ ★ ▲ │★ ▲ 1e3 ┤ ▲ │▲ 10 ┼────┬────┬────┬────┬────→ n 0 10 50 100 500 1000 ★ = 指数 ▲ = 立方 ● = 平方 ■ = nlogn ◆ = 线性 ◇ = 对数

5.3 复杂度分析实战

示例1：单层循环

defexample1(arr):"""时间复杂度：O(n)"""total=0fornuminarr:# 执行 n 次total+=numreturntotal

示例2：双层循环

defexample2(arr):"""时间复杂度：O(n²)"""count=0foriinarr:# 执行 n 次forjinarr:# 每次执行 n 次ifi+j==0:count+=1returncount# 总操作：n × n = n²

示例3：循环折半

defexample3(n):"""时间复杂度：O(log n)"""count=0whilen>0:# n 每次减半n=n//2count+=1returncount# n=16: 16→8→4→2→1，执行4次 = log₂16# n=1024: 执行10次 = log₂1024

示例4：递归

defexample4(n):"""时间复杂度：O(2ⁿ)"""ifn<=1:return1returnexample4(n-1)+example4(n-1)# 调用树：# f(4)# / \# f(3) f(3)# / \ / \# f(2) f(2) f(2) f(2)# ... 共 2⁴ - 1 = 15 个节点

5.4 空间复杂度

defsum_iterative(n):"""空间复杂度：O(1)"""total=0foriinrange(1,n+1):total+=ireturntotaldefsum_recursive(n):"""空间复杂度：O(n) - 调用栈深度"""ifn==1:return1returnn+sum_recursive(n-1)defcreate_matrix(n):"""空间复杂度：O(n²)"""return[[0]*nfor_inrange(n)]

6. Python 实现经典算法

6.1 搜索算法

线性搜索：O(n)

deflinear_search(arr,target):"""逐个查找，最坏遍历全部"""fori,numinenumerate(arr):ifnum==target:returni# 找到，返回索引return-1# 未找到# 适用：无序数据，数据量小

二分搜索：O(log n)

defbinary_search(arr,target):""" 二分搜索：每次排除一半数据 前提：数组必须有序！ """left,right=0,len(arr)-1whileleft<=right:mid=(left+right)//2ifarr[mid]==target:returnmid# 找到！elifarr[mid]<target:left=mid+1# 目标在右半区else:right=mid-1# 目标在左半区return-1# 未找到# 测试sorted_arr=[1,3,5,7,9,11,13,15,17,19]print(binary_search(sorted_arr,7))# 3print(binary_search(sorted_arr,10))# -1# 性能对比：# 线性搜索 100万个元素：最坏100万次比较# 二分搜索 100万个元素：最多20次比较！

6.2 排序算法

选择排序：O(n²)

defselection_sort(arr):""" 思路：每次从未排序区选最小，放到已排序区末尾 """n=len(arr)foriinrange(n):min_idx=iforjinrange(i+1,n):ifarr[j]<arr[min_idx]:min_idx=j arr[i],arr[min_idx]=arr[min_idx],arr[i]returnarr# 直观但低效，仅用于教学

快速排序：O(n log n) 平均

defquick_sort(arr):""" 分治策略： 1. 选基准（pivot） 2. 分区：小于放左，大于放右 3. 递归排序左右子数组 """iflen(arr)<=1:returnarr pivot=arr[len(arr)//2]# 选中间元素为基准left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)# 测试arr=[64,34,25,12,22,11,90]print(quick_sort(arr))# [11, 12, 22, 25, 34, 64, 90]

归并排序：稳定 O(n log n)

defmerge_sort(arr):"""分治：先分后合"""iflen(arr)<=1:returnarr mid=len(arr)//2left=merge_sort(arr[:mid])right=merge_sort(arr[mid:])returnmerge(left,right)defmerge(left,right):"""合并两个有序数组"""result=[]i=j=0whilei<len(left)andj<len(right):ifleft[i]<=right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1result.extend(left[i:])result.extend(right[j:])returnresult

6.3 排序算法性能对比

importrandomimporttimedefcompare_sorts():"""对比不同排序算法的实际性能"""algorithms={"选择排序":selection_sort,"快速排序":quick_sort,"归并排序":merge_sort,"Python内置":sorted,}sizes=[100,1000,5000]print(f"{'规模':>8}",end="")fornameinalgorithms:print(f"{name:>12}",end="")print()print("-"*60)forsizeinsizes:arr=[random.randint(1,10000)for_inrange(size)]print(f"{size:>8}",end="")forname,funcinalgorithms.items():test_arr=arr.copy()start=time.time()func(test_arr)elapsed=time.time()-startprint(f"{elapsed:>11.4f}s",end="")print()compare_sorts()

典型输出：

规模 选择排序 快速排序 归并排序 Python内置 ------------------------------------------------------------ 100 0.0012s 0.0003s 0.0004s 0.0000s 1000 0.0891s 0.0021s 0.0032s 0.0001s 5000 2.3124s 0.0123s 0.0187s 0.0008s

💡为什么内置 sorted 最快？Python 的sorted()使用Timsort，是归并排序+插入排序的混合算法，针对真实数据高度优化。

7. 算法思维：从解题到创造

7.1 五大经典算法思想

┌─────────────────────────────────────────────────────┐ │ 1. 枚举（暴力） │ │ 尝试所有可能，保证正确性 │ │ 例：密码破解、全排列 │ ├─────────────────────────────────────────────────────┤ │ 2. 分治（Divide and Conquer） │ │ 大问题拆成小问题，分别解决后合并 │ │ 例：归并排序、快速排序、二分查找 │ ├─────────────────────────────────────────────────────┤ │ 3. 贪心（Greedy） │ │ 每一步选当前最优，期望全局最优 │ │ 例：找零钱、活动安排、最小生成树 │ ├─────────────────────────────────────────────────────┤ │ 4. 动态规划（Dynamic Programming） │ │ 大问题依赖子问题，子问题重叠，记忆化存储 │ │ 例：斐波那契、背包问题、最长公共子序列 │ ├─────────────────────────────────────────────────────┤ │ 5. 回溯（Backtracking） │ │ 深度搜索+剪枝，试探性解决问题 │ │ 例：八皇后、迷宫、数独、全排列 │ └─────────────────────────────────────────────────────┘

7.2 算法思维训练：从"怎么做"到"为什么"

初级：知道怎么做

# 题目：两数之和deftwo_sum(nums,target):foriinrange(len(nums)):forjinrange(i+1,len(nums)):ifnums[i]+nums[j]==target:return[i,j]return[]# 能跑，但 O(n²)

进阶：知道为什么慢

# 优化：用哈希表，O(n)deftwo_sum_optimized(nums,target):seen={}fori,numinenumerate(nums):complement=target-numifcomplementinseen:return[seen[complement],i]seen[num]=ireturn[]# 用空间换时间，从 O(n²) 降到 O(n)

高级：知道还能不能更好

# 如果数组已排序？双指针，O(n)，空间 O(1)deftwo_sum_sorted(nums,target):left,right=0,len(nums)-1whileleft<right:s=nums[left]+nums[right]ifs==target:return[left,right]elifs<target:left+=1else:right-=1return[]

🎯算法思维的核心：面对问题，先想"最优解是什么"，再想"怎么实现"，而不是"先写出来再说"。

8. 结语：算法之美

“算法 + 数据结构 = 程序”—— Niklaus Wirth（图灵奖得主）

算法不是冰冷的代码，它是人类智慧的结晶。

当你写出第一个二分查找，你会惊叹：原来可以这么快！
当你理解动态规划，你会感叹：子问题重叠的优雅！
当你解决汉诺塔，你会震撼：递归分解的力量！

为什么每个人都该学算法？

1. 训练逻辑思维：像计算机一样严谨思考
2. 提升问题解决能力：面对复杂问题不再无从下手
3. 打开职业大门：技术面试的通行证
4. 理解世界：推荐系统、导航、AI 背后的原理
5. 纯粹的智力愉悦：就像解出一道数学难题

🌟最后的话：

算法学习没有捷径，但有方法。不要畏惧困难，每一道你攻克的题目，都在重塑你的大脑。从今天开始，每天进步一点点，一年后你会感谢现在的自己。

记住：

• 看懂 ≠ 会写
• 会写 ≠ 熟练
• 熟练 ≠ 创新

从模仿到创造，从练习到精通。算法之路，始于足下。