Python算法基础
算法概述
算法是解决特定问题的一系列步骤。好的算法应该具备以下特征： - 输入：有零个或多个输入 - 输出：至少有一个输出 - 有穷性：在有限步骤内完成 - 确定性：每个步骤都是明确的 - 可行性：每个步骤都是可执行的
1 时间复杂度
时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势，“时间增长趋势”这个概念比较抽象，通过一个例子来加以理解。假设输入数据大小为 𝑛 ，给定三个算法 A、B 和 C ：
# 算法 A 的时间复杂度：常数阶
def algorithm_A(n: int):
print(0)
# 算法 B 的时间复杂度：线性阶
def algorithm_B(n: int):
for _ in range(n):
print(0)
# 算法 C 的时间复杂度：常数阶
def algorithm_C(n: int):
for _ in range(1000000):
print(0)
1.1 常数阶 𝑂(1)
常数阶的操作数量与输入数据大小 𝑛 无关，即不随着 𝑛 的变化而变化。在以下函数中，尽管操作数量 size 可能很大，但由于其与输入数据大小 𝑛 无关，因此时间复杂度仍为 𝑂(1) ：
def constant(n):
"""常数阶"""
count = 0
size = 100000
for _ in range(size):
count += 1
return count
#实例：
print(constant(3)) #100000
print(constant(50)) #100000
#说明常数阶的操作数量与输入数据大小n无关
1.2 线性阶 𝑂(𝑛)
线性阶的操作数量相对于输入数据大小 𝑛 以线性级别增长。线性阶通常出现在单层循环中：
def linear(n):
"""线性阶"""
count = 0
for _ in range(n):
count += 1
return count
#实例：
print(linear(3)) #3
print(linear(50)) #50
#说明常数阶的操作数量与输入大小n有关
1.3 平方阶 𝑂(𝑛^2)
平方阶的操作数量相对于输入数据大小 𝑛 以平方级别增长。平方阶通常出现在嵌套循环中，外层循环和内层循环的时间复杂度都为 𝑂(𝑛) ，因此总体的时间复杂度为 𝑂(𝑛^2) ：
def quadratic(n):
"""平方阶"""
count = 0
# 循环次数与数据大小 n 成平方关系
for i in range(n):
for j in range(n):
count += 1
return count
#实例：
print(quadratic(4)) #16
print(quadratic(15)). #25
1.4 指数阶 𝑂(2^𝑛)
生物学的“细胞分裂”是指数阶增长的典型例子：初始状态为 1 个细胞，分裂一轮后变为 2 个，分裂两轮后变为 4 个，以此类推，分裂 𝑛 轮后有 2^𝑛 个细胞。 以下代码模拟了细胞分裂的过程，时间复杂度为 𝑂(2^𝑛) 。请注意，输入 𝑛 表示分裂轮数，返回值 count 表示总分裂次数。
def exponential(n: int) -> int:
"""指数阶（循环实现）"""
count = 0
base = 1
# 细胞每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)
for _ in range(n):
for _ in range(base):
count += 1
base *= 2
# count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
return count
#实例：
print(exponential(4)) #15
print(exponential(5)) #31
2 排序算法
2.1 冒泡排序
冒泡排序（Bubble Sort）算法，它的核心思想是重复遍历待排序的数列，一次比较两个元素，如果顺序错误就把它们交换过来，直到整个数列有序。 冒泡排序的基本步骤是： 1. 比较相邻元素：从第一个元素开始，依次比较相邻的两个元素。 2. 交换元素：如果顺序错误（例如升序排列时前一个元素大于后一个元素），则交换它们。 3. 重复步骤 1-2：对每一对相邻元素重复上述过程，直到最后一对。 4. 优化：每一轮比较后，最大的元素会 "浮" 到数列末尾，因此下一轮可以少比较一个元素。 冒泡排序算法如下：
def bubble_sort(arr):
n = len(arr) # 获取数组长度
for i in range(n): # 外层循环：控制排序轮数，共需要n-1轮
for j in range(n-1-i): # 内层循环：每轮比较的次数逐渐减少,也可以range(n-1),不过计算量大一些
if arr[j] > arr[j+1]: # 比较相邻元素
arr[j], arr[j+1] = arr[j+1], arr[j] # 交换元素
return arr # 返回排序后的数组
arr = [2,3,6,5,3,2,1]
print(maopao(arr))
#结果
#[1, 2, 2, 3, 3, 5, 6]
2.2 选择排序
选择排序（Selection Sort）算法，它的核心思想是每一轮从未排序部分中选出最小元素，与未排序部分的第一个元素交换位置，直到整个数组有序。 选择排序的基本步骤是： 1. 划分数组：将数组分为已排序部分（初始为空）和未排序部分。 2. 寻找最小值：在未排序部分中找到最小的元素。 3. 交换元素：将找到的最小值与未排序部分的第一个元素交换。 4. 扩展已排序部分：已排序部分增加一个元素，未排序部分减少一个元素。 5. 重复步骤 2-4：直到未排序部分为空。
def select_sort(arr):
n = len(arr) # 获取数组长度
for i in range(n): # 外层循环：控制当前未排序部分的起始位置
min_index = i # 假设当前位置的元素是最小值
for j in range(i+1, n): # 内层循环：在未排序部分中寻找最小值
if arr[j] < arr[min_index]: # 如果找到更小的元素
min_index = j # 更新最小值的索引
arr[min_index], arr[i] = arr[i], arr[min_index] # 交换最小值和当前位置的元素
return arr # 返回排序后的数组
# 测试代码
arr = [2, 3, 6, 5, 3, 2, 1]
print(select_sort(arr))
# 输出：[1, 2, 2, 3, 3, 5, 6]
2.3 拆入排序
插入排序（Insertion Sort）核心思想是将未排序数据逐个插入到已排序序列的适当位置。它类似于玩扑克牌时整理手牌的方式 —— 每次拿到一张新牌，就将其插入到已有牌的正确位置。 算法步骤： 1. 划分数组：将数组分为已排序部分（初始为第一个元素）和未排序部分。 2. 选择元素：从未排序部分取出第一个元素，称为当前元素。 3. 寻找插入位置：在已排序部分中，从后向前比较，找到第一个小于或等于当前元素的位置。 4. 插入元素：将当前元素插入到该位置，已排序部分长度加 1。 5. 重复步骤 2-4：直到未排序部分为空。
def insertion_sort(arr):
for i in range(1, len(arr)): # 从第2个元素开始遍历（索引1）
key = arr[i] # 当前要插入的元素
j = i - 1 # 已排序部分的最后一个元素索引
# 将比key大的元素后移
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # 元素后移
j -= 1
# 插入key
arr[j + 1] = key
return arr
# 测试示例
arr = [5, 2, 4, 6, 1, 3]
print(insertion_sort(arr)) # 输出: [1, 2, 3, 4, 5, 6]
3 查找算法
3.1 线性查找
线性查找（Linear Search），也称为顺序查找，是一种最简单的搜索算法。它的核心思想是逐个遍历数据结构中的元素，直到找到目标值或遍历完所有元素。 算法步骤： 1. 从第一个元素开始：从数据结构（如数组、列表）的起始位置开始遍历。 2. 逐个比较：将当前元素与目标值进行比较。 3. 返回结果： - 如果找到匹配的元素，返回其位置（索引）。 - 如果遍历完所有元素仍未找到，返回特定值（如 -1 或 None）表示未找到。 代码如下所示：
def linear_search(arr, target):
"""
线性查找算法实现
参数:
arr (list): 待查找的列表
target: 要查找的目标值
返回:
int: 目标值在列表中的索引，如果未找到返回 -1
"""
for i in range(len(arr)):
if arr[i] == target:
return i # 找到目标值，返回索引
return -1 # 未找到目标值
# 测试示例
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
target = 9
result = linear_search(arr, target)
if result != -1:
print(f"目标值 {target} 在索引 {result} 处找到")
else:
print(f"目标值 {target} 未找到")
#结果为：目标值 9 在索引 5 处找到
3.2 二分查找
二分查找是一种高效的搜索算法，适用于已排序的数据结构（如有序数组）。其核心思想是每次将搜索范围缩小一半，直到找到目标值或确定目标值不存在。 算法步骤： 1. 确定中间点：计算当前搜索范围的中间位置。 2. 比较中间值：将中间位置的元素与目标值比较： - 若相等，则找到目标值。 - 若中间值大于目标值，缩小搜索范围到左半部分。 - 若中间值小于目标值，缩小搜索范围到右半部分。 3. 重复步骤 a-b：直到找到目标值或搜索范围为空。
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 # 未找到目标值
# 测试示例
arr = [1, 3, 4, 5, 9, 12, 15]
target = 9
print(binary_search(arr, target)) # 输出: 4（目标值的索引位置）
4 递归算法
递归是一种 “自己调用自己” 的编程技巧，需注意 终止条件 和 递推关系。
4.1 阶乘
递归解决阶乘的关键在于递推关系和终止条件： 1. 终止条件：当 n = 0 时，直接返回 1，不再继续递归。 2. 递推关系：n! = n × (n-1)!，即把 n! 的计算分解为 n 乘以 (n-1)! 的子问题。 代码实例如下所示：
def factorial(n):
if n==0:
return 1
return n*factorial(n-1)
print(factorial(5)) #输出：120
print(factorial(10)) #输出：3628800
4.2 斐波那契数列
def fibonacci(n):
if n == 0: # 终止条件1：n=0时返回0
return 0
elif n == 1: # 终止条件2：n=1时返回1
return 1
else: # 递推关系：f(n) = f(n-1) + f(n-2)
return fibonacci(n-1) + fibonacci(n-2)
#斐波那契数列的前10项为[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
# 测试
print(fibonacci(5)) # 输出: 5（序列：0,1,1,2,3,5）
print(fibonacci(10)) # 输出: 55
5 字符串处理算法
5.1 反转字符串
# 切片法（一行实现）
reversed_str = s[::-1]
#实例：
s = 'hello'
print(s[::-1])
#输出：olleh
# 双指针法（原地反转，适合列表）
def reverse_string(s_list):
left, right = 0, len(s_list)-1
while left < right:
s_list[left], s_list[right] = s_list[right], s_list[left]
left += 1
right -= 1
return s_list
#实例：
string_list = ['hello','world','apple','peach','tap4fun']
print(reverse_string(string_list))
#输出：['tap4fun', 'peach', 'apple', 'world', 'hello']
5.2 判断回文
思想：字符串正序和逆序是否相等，代码如下所示
def is_palindrome(str):
if str == str[::-1]:
return True
return False
#实例：
str_1 = 'string'
str_2 = 'holloh'
print(is_palindrome(str_1)) #输出： Fasle
print(is_palindrome(str_2)) #输出：True
6 简单的算法思想
6.1 模拟算法
模拟算法的思想：按题意模拟过程，如 “猜数字游戏”“银行排队” 等。如下实例，模拟投掷n次骰子后，点数统计情况：
import random
count = [0]*7 #索引0不用，1-6对应点数
def count_sum(n):
for _ in range(n):
point = random.randint(1,6)
count[point] += 1
return count[1:7]
print(count_sum(180)) #输出：[25, 28, 33, 32, 31, 31]
6.2 贪心算法
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优（局部最优）的选择，从而希望最终导致全局最优解的算法策略。它不考虑整体情况，仅关注当前步骤的最优解，因此适用于具有贪心选择性质和最优子结构性质的问题。 贪心算法的核心思想如下： 1. 贪心选择：每一步都做出当前看起来最优的选择，不考虑该选择对后续步骤的影响。 2. 局部最优 → 全局最优：通过每一步的局部最优选择，最终达到全局最优解。 经典案例：找零问题 问题描述：给定面额为 1、5、10、25 的硬币，如何用最少的硬币凑出指定金额？ 贪心策略：每次选择面值最大的硬币，直到凑出目标金额。 代码如下：
def coin_change(amount):
coins = [25, 10, 5, 1] # 硬币面值（降序排列）
count = [0]*len(coins) # 各面值硬币数量
for coin in coins:
if amount >= coin:
num = amount // coin # 当前面值的硬币数量
count[coins.index(coin)] = num
amount -= num * coin # 剩余金额
if amount == 0:
break
return count
# 测试
print(coin_change(63))
# 输出 [2, 1, 0, 3]
#即（25×2 + 10×1 + 5×0 + 1×3）
7 算法优化技巧
7.1 空间时间权衡
# 使用额外空间换取时间效率
def two_sum(nums, target):
seen = {} # 空间换时间
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
7.2 循环优化
# 减少循环中的计算
def optimize_loop():
n = 1000
# 优化前
for i in range(n):
result = i * len(range(n)) # 每次都计算len
# 优化后
length = len(range(n)) # 提前计算
for i in range(n):
result = i * length
7.3 使用适当的数据结构
# 使用集合进行快速查找
def find_duplicate(nums):
seen = set()
for num in nums:
if num in seen: # O(1)查找
return num
seen.add(num)
return None
练习题
- 实现一个函数，判断一个字符串是否是回文
- 编写一个函数，找出数组中第k大的元素
- 实现一个简单的计算器，支持基本的四则运算和括号
进阶主题
- 动态规划
- 贪心算法
- 回溯算法
- 图算法
- 树算法
小结
- 理解算法的基本概念和特征
- 掌握时间复杂度分析方法
- 能够实现基本的查找和排序算法
- 理解递归的原理和应用
- 掌握基本的算法优化技巧