当前位置: 首页 > news >正文

Python 学习之路(十)--常见算法实现原理及解析

文章目录

        • 1. **排序算法**
          • (1) 冒泡排序(Bubble Sort)
          • (2) 快速排序(Quick Sort)
          • (3) 归并排序(Merge Sort)
        • 2. **查找算法**
          • (1) 线性查找(Linear Search)
          • (2) 二分查找(Binary Search)
        • 3. **图算法**
          • (1) 深度优先搜索(DFS)
          • (2) 广度优先搜索(BFS)
        • 4. **动态规划算法**
          • 背包问题(Knapsack Problem)

1. 排序算法
(1) 冒泡排序(Bubble Sort)

原理:
冒泡排序是一种简单的排序算法,它通过重复遍历列表,比较相邻的元素并交换它们的位置,直到整个列表有序为止。每一轮遍历会将最大的元素“冒泡”到列表末尾。

代码实现:

def bubble_sort(arr):n = len(arr)for i in range(n):# 每次遍历时,最后i个元素已排序完成,无需再比较for j in range(0, n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr

时间复杂度:

  • 最坏情况:O(n²)(当列表完全逆序)
  • 平均情况:O(n²)
  • 最好情况:O(n)(如果列表已经有序,可以通过优化提前终止)

优化方法:
添加一个标志位,如果某一轮没有发生任何交换,说明列表已经有序,可以直接退出循环。


(2) 快速排序(Quick Sort)

原理:
快速排序是一种分治法(Divide and Conquer)的经典应用。它选择一个基准元素(pivot),将数组分为两个子数组:一部分小于基准值,另一部分大于基准值。然后对这两个子数组递归地进行快速排序。

代码实现:

def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]  # 选择中间元素作为基准left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)

时间复杂度:

  • 最坏情况:O(n²)(当每次划分极不平衡时)
  • 平均情况:O(n log n)

优化方法:
随机选择基准值或三数取中法,避免最坏情况的发生。


(3) 归并排序(Merge Sort)

原理:
归并排序也是分治法的一种。它将数组分成两半,分别对两半进行排序,然后将排好序的两半合并成一个有序数组。

代码实现:

def merge_sort(arr):if len(arr) <= 1:return arrdef merge(left, right):result = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result.extend(left[i:])result.extend(right[j:])return resultmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)

时间复杂度:

  • 最坏情况:O(n log n)
  • 平均情况:O(n log n)

优点:
稳定排序,适合链表结构等应用场景。


2. 查找算法
(1) 线性查找(Linear Search)

原理:
线性查找是最基本的查找方式,从头开始逐个检查元素,直到找到目标元素或遍历完整个列表。

代码实现:

def linear_search(arr, target):for i, val in enumerate(arr):if val == target:return ireturn -1

时间复杂度:

  • 最坏情况:O(n)
  • 平均情况:O(n)

适用场景:
无序列表或数据量较小的情况。


(2) 二分查找(Binary Search)

原理:
二分查找适用于有序列表。它通过不断缩小搜索范围,将目标值与中间元素比较,若目标值小于中间元素,则在左半部分继续查找;否则在右半部分查找。

代码实现:

def binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return midelif arr[mid] < target:low = mid + 1else:high = mid - 1return -1

时间复杂度:

  • 最坏情况:O(log n)
  • 平均情况:O(log n)

适用场景:
有序列表中的高效查找。


3. 图算法
(1) 深度优先搜索(DFS)

原理:
深度优先搜索是一种用于遍历或搜索树、图的算法。它沿着一条路径尽可能深入地探索,直到无法继续前进,然后回溯。

代码实现:

def dfs(graph, start, visited=None):if visited is None:visited = set()visited.add(start)print(start)for neighbor in graph[start]:if neighbor not in visited:dfs(graph, neighbor, visited)

时间复杂度:

  • O(V + E),其中 V 是顶点数,E 是边数。

(2) 广度优先搜索(BFS)

原理:
广度优先搜索按层遍历图,首先访问起始节点的所有邻居,然后再访问邻居的邻居,依此类推。

代码实现:

from collections import dequedef bfs(graph, start):visited = set()queue = deque([start])visited.add(start)while queue:node = queue.popleft()print(node)for neighbor in graph[node]:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)

时间复杂度:

  • O(V + E)

4. 动态规划算法
背包问题(Knapsack Problem)

原理:
动态规划是一种解决复杂问题的方法,通常用于具有重叠子问题和最优子结构的问题。背包问题是经典的动态规划问题之一,目标是在容量限制下最大化物品价值。

代码实现:

def knapsack(weights, values, capacity):n = len(values)dp = [[0] * (capacity + 1) for _ in range(n + 1)]for i in range(1, n + 1):for w in range(capacity + 1):if weights[i - 1] <= w:dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])else:dp[i][w] = dp[i - 1][w]return dp[n][capacity]

时间复杂度:

  • O(n * capacity)
http://www.xdnf.cn/news/1116217.html

相关文章:

  • 深度学习-循环神经网络RNN
  • 谷歌推出Vertex AI Memory Bank:为AI智能体带来持久记忆,支持连续对话
  • MongoDB性能优化实战指南:原理、实践与案例
  • RedisJSON 技术揭秘(五)`JSON.ARRPOP` 原子弹出 修改数组的终极手段
  • Java设计模式之行为型模式(命令模式)介绍与说明
  • 串口A和S的含义以及RT的含义
  • 深入理解观察者模式:构建松耦合的交互系统
  • 设计模式深度解析:单例、工厂、适配器与代理模式
  • Word中的批注显示与修订显示
  • STM32 | HC-SR04 超声波传感器测距
  • 洛谷 P13014:[GESP202506 五级] 最大公因数
  • CentOS系统下前后端项目部署攻略
  • 【MLLM】多模态理解GLM-4.1V-Thinking模型
  • 深度学习图像分类数据集—水质量识别分类
  • java.net.InetAddress
  • Extended Nested Arrays for Consecutive Virtual Aperture Enhancement
  • RHCIA第二次综合实验:OSPF
  • 印度纱丽变革:传统靛蓝工艺在无性别斗篷中的延续
  • CMSIS(Cortex Microcontroller Software Interface Standard)ARM公司为 Cortex-M 系列处理器
  • docker 设置代理以及配置镜像加速
  • VISUALBERT:一个简单且高效的视觉与语言基线模型
  • JavaScript加强篇——第九章 正则表达式高级应用(终)
  • java+vue+SpringBoo中小型制造企业质量管理系统(程序+数据库+报告+部署教程+答辩指导)
  • archive/tar: unknown file mode ?rwxr-xr-x
  • Java行为型模式---策略模式
  • 低代码引擎核心技术:OneCode常用动作事件速查手册及注解驱动开发详解
  • 2023.05.06 更新前端面试问题总结(12道题)
  • VsCode的LivePreview插件应用
  • 【hivesql 已知维度父子关系加工层级表】
  • Pytorch实现感知器并实现分类动画