Python 基础算法介绍目录算法与复杂度分析1.1 什么是算法1.2 时间复杂度1.3 空间复杂度排序算法2.1 冒泡排序2.2 选择排序2.3 插入排序2.4 归并排序2.5 快速排序搜索算法3.1 线性搜索3.2 二分搜索递归与分治4.1 递归的基本思想4.2 分治法的步骤与实例动态规划5.1 动态规划的核心概念5.2 经典问题斐波那契数列5.3 经典问题0/1 背包问题贪心算法6.1 贪心策略6.2 经典问题找零钱6.3 经典问题活动选择图算法基础7.1 图的表示7.2 广度优先搜索BFS7.3 深度优先搜索DFS常用技巧与总结1. 算法与复杂度分析1.1 什么是算法算法Algorithm是解决特定问题的一系列明确、有限的步骤。对相同输入算法会给出相同输出并能在有限时间内完成。1.2 时间复杂度时间复杂度描述算法的执行时间随输入规模增长的变化趋势常用大O符号表示如O(1)常数时间O(log n)对数时间O(n)线性时间O(n²)平方时间O(2^n)指数时间1.3 空间复杂度空间复杂度衡量算法运行过程中临时占用的存储空间大小同样使用大O表示法。2. 排序算法2.1 冒泡排序Bubble Sort反复遍历列表比较相邻元素并交换顺序错误者每一轮将最大或最小元素“浮”到顶端。时间复杂度O(n²)空间复杂度O(1)。defbubble_sort(arr):nlen(arr)foriinrange(n):forjinrange(0,n-i-1):ifarr[j]arr[j1]:arr[j],arr[j1]arr[j1],arr[j]returnarr2.2 选择排序Selection Sort每次从未排序部分找出最小元素放到已排序部分的末尾。时间复杂度O(n²)空间复杂度O(1)。defselection_sort(arr):nlen(arr)foriinrange(n):min_idxiforjinrange(i1,n):ifarr[j]arr[min_idx]:min_idxj arr[i],arr[min_idx]arr[min_idx],arr[i]returnarr2.3 插入排序Insertion Sort将数组分为已排序和未排序两部分每次取未排序部分第一个元素插入到已排序部分的正确位置。时间复杂度O(n²)空间复杂度O(1)对近乎有序的数据效率高。definsertion_sort(arr):foriinrange(1,len(arr)):keyarr[i]ji-1whilej0andarr[j]key:arr[j1]arr[j]j-1arr[j1]keyreturnarr2.4 归并排序Merge Sort采用分治策略将数组递归分成两半分别排序后再合并。时间复杂度O(n log n)空间复杂度O(n)。defmerge_sort(arr):iflen(arr)1:returnarr midlen(arr)//2leftmerge_sort(arr[:mid])rightmerge_sort(arr[mid:])returnmerge(left,right)defmerge(left,right):result[]ij0whileilen(left)andjlen(right):ifleft[i]right[j]:result.append(left[i])i1else:result.append(right[j])j1result.extend(left[i:])result.extend(right[j:])returnresult2.5 快速排序Quick Sort选择一个基准元素将数组划分为小于和大于基准的两部分然后递归排序。平均时间复杂度O(n log n)最坏 O(n²)空间复杂度O(log n)递归栈。defquick_sort(arr):iflen(arr)1:returnarr pivotarr[len(arr)//2]left[xforxinarrifxpivot]middle[xforxinarrifxpivot]right[xforxinarrifxpivot]returnquick_sort(left)middlequick_sort(right)3. 搜索算法3.1 线性搜索Linear Search依次检查每个元素找到目标则返回索引。时间复杂度O(n)空间复杂度O(1)。deflinear_search(arr,target):fori,valinenumerate(arr):ifvaltarget:returnireturn-13.2 二分搜索Binary Search要求数组有序。每次将搜索范围缩小一半通过比较中间元素与目标值决定继续向左或向右搜索。时间复杂度O(log n)空间复杂度O(1)迭代版或 O(log n)递归版。defbinary_search(arr,target):left,right0,len(arr)-1whileleftright:mid(leftright)//2ifarr[mid]target:returnmidelifarr[mid]target:leftmid1else:rightmid-1return-14. 递归与分治4.1 递归的基本思想递归是函数直接或间接调用自身。关键要素基线条件停止递归递归条件将问题分解为更小的子问题4.2 分治法的步骤与实例分治法将问题分成若干子问题分别求解最后合并结果。归并排序和快速排序都是典型代表。示例计算数组元素之和。defsum_recursive(arr):ifnotarr:return0returnarr[0]sum_recursive(arr[1:])5. 动态规划5.1 动态规划的核心概念动态规划DP通过存储子问题的解避免重复计算适用于具有重叠子问题和最优子结构性质的问题。常用方法自顶向下记忆化递归自底向上迭代填表5.2 经典问题斐波那契数列Fibonacci 数列F(0)0, F(1)1, F(n)F(n-1)F(n-2)。用 DP 优化deffib_dp(n):ifn1:returnn dp[0]*(n1)dp[1]1foriinrange(2,n1):dp[i]dp[i-1]dp[i-2]returndp[n]时间复杂度 O(n)空间复杂度 O(n)可优化为 O(1)。5.3 经典问题0/1 背包问题给定物品重量和价值在背包容量限制下最大化总价值。状态定义dp[i][w]表示前 i 件物品在容量 w 下的最大价值。转移方程dp[i][w] max(dp[i-1][w], dp[i-1][w-wt[i]] val[i])。defknapsack(values,weights,capacity):nlen(values)dp[[0]*(capacity1)for_inrange(n1)]foriinrange(1,n1):forwinrange(1,capacity1):ifweights[i-1]w:dp[i][w]dp[i-1][w]else:dp[i][w]max(dp[i-1][w],dp[i-1][w-weights[i-1]]values[i-1])returndp[n][capacity]6. 贪心算法6.1 贪心策略贪心算法每步选择当前最优解希望最终得到全局最优。它不总是有效但在一些问题如最小生成树、最短路径中可以得到最优解。6.2 经典问题找零钱假设硬币面额满足贪心性质如人民币用最少硬币找零defmin_coins(coins,amount):coins.sort(reverseTrue)count0forcoinincoins:ifamountcoin:numamount//coin countnum amount-num*coinreturncountifamount0else-16.3 经典问题活动选择给定一系列活动的开始和结束时间选出最多不冲突的活动。贪心策略每次选结束时间最早且不与已选活动冲突的活动。defactivity_selection(activities):# activities 为 (start, end) 列表activities.sort(keylambdax:x[1])selected[]last_end0forstart,endinactivities:ifstartlast_end:selected.append((start,end))last_endendreturnselected7. 图算法基础7.1 图的表示邻接矩阵graph[i][j]表示边的权重邻接表字典或列表graph[node]存储邻居节点7.2 广度优先搜索BFS使用队列逐层遍历常用于求最短路径无权图。fromcollectionsimportdequedefbfs(graph,start):visitedset()queuedeque([start])visited.add(start)whilequeue:nodequeue.popleft()print(node,end )forneighboringraph[node]:ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)7.3 深度优先搜索DFS尽可能深地访问节点使用递归或栈实现。defdfs(graph,node,visitedNone):ifvisitedisNone:visitedset()visited.add(node)print(node,end )forneighboringraph[node]:ifneighbornotinvisited:dfs(graph,neighbor,visited)8. 常用技巧与总结双指针在有序数组中寻找两数之和等场景应用广泛。滑动窗口用于求满足条件的连续子数组串。前缀和快速计算区间和常用于数组问题。位运算提高效率处理子集、状态压缩等问题。
