Python进阶教程：算法与数据结构入门

目录Python进阶教程算法与数据结构入门一、时间复杂度二、常用数据结构2.1 列表与字典2.2 栈Stack2.3 队列Queue三、排序算法3.1 冒泡排序O(n²)3.2 快速排序O(n log n)四、查找算法五、递归六、动态规划入门七、实战实现 LRU 缓存总结Python进阶教程算法与数据结构入门本文是Python 入门教程系列的第 18 篇扩展篇。算法与数据结构是编程的内功本篇介绍最核心的几种用 Python 实现。一、时间复杂度衡量算法效率用大 O 表示法描述执行时间随数据规模增长的速度复杂度含义示例O(1)常数时间数组按下标访问O(log n)对数时间二分查找O(n)线性时间遍历列表O(n log n)线性对数快速排序O(n²)平方时间冒泡排序二、常用数据结构2.1 列表与字典# 列表有序、可重复fruits[苹果,香蕉,橙子]fruits.append(葡萄)print(fruits[0],len(fruits))# 字典键值对、查找 O(1)scores{张三:90,李四:85}print(scores[张三])print(scores.get(王五,不存在))2.2 栈Stack# 栈后进先出LIFO用列表实现stack[]stack.append(1)# 入栈stack.append(2)stack.append(3)print(stack.pop())# 3 出栈print(stack[-1])# 2 查看栈顶print(len(stack)0)# 判断是否为空2.3 队列Queuefromcollectionsimportdeque# 队列先进先出FIFOqueuedeque([a,b,c])queue.append(d)# 入队print(queue.popleft())# a 出队print(queue)# deque([b, c, d])三、排序算法3.1 冒泡排序O(n²)defbubble_sort(arr):nlen(arr)foriinrange(n-1):forjinrange(n-1-i):ifarr[j]arr[j1]:arr[j],arr[j1]arr[j1],arr[j]returnarrprint(bubble_sort([5,2,8,1,9]))# [1, 2, 5, 8, 9]3.2 快速排序O(n log n)defquick_sort(arr):iflen(arr)1:returnarr pivotarr[len(arr)//2]left[xforxinarrifxpivot]mid[xforxinarrifxpivot]right[xforxinarrifxpivot]returnquick_sort(left)midquick_sort(right)print(quick_sort([5,2,8,1,9]))# [1, 2, 5, 8, 9]四、查找算法# 二分查找要求有序O(log n)defbinary_search(arr,target):left,right0,len(arr)-1whileleftright:mid(leftright)//2ifarr[mid]target:returnmidelifarr[mid]target:leftmid1else:rightmid-1return-1nums[1,3,5,7,9,11]print(binary_search(nums,7))# 3print(binary_search(nums,8))# -1五、递归# 递归函数调用自身deffactorial(n):ifn1:return1returnn*factorial(n-1)print(factorial(5))# 120# 斐波那契带缓存避免重复计算fromfunctoolsimportlru_cachelru_cache(maxsizeNone)deffib(n):ifn2:returnnreturnfib(n-1)fib(n-2)print(fib(50))# 12586269025六、动态规划入门# 经典问题爬楼梯每次 1 或 2 阶defclimb_stairs(n):ifn2:returnn dp[0]*(n1)dp[1],dp[2]1,2foriinrange(3,n1):dp[i]dp[i-1]dp[i-2]returndp[n]print(climb_stairs(10))# 89七、实战实现 LRU 缓存fromcollectionsimportOrderedDictclassLRUCache:最近最少使用缓存def__init__(self,capacity):self.cacheOrderedDict()self.capacitycapacitydefget(self,key):ifkeynotinself.cache:return-1self.cache.move_to_end(key)# 标记为最近使用returnself.cache[key]defput(self,key,value):ifkeyinself.cache:self.cache.move_to_end(key)self.cache[key]valueiflen(self.cache)self.capacity:self.cache.popitem(lastFalse)# 淘汰最久未用cacheLRUCache(2)cache.put(1,A)cache.put(2,B)print(cache.get(1))# Acache.put(3,C)# 淘汰 key2print(cache.get(2))# -1print(cache.get(3))# C总结本篇介绍了时间复杂度、常用数据结构栈、队列、排序与查找算法、递归和动态规划入门并用 LRU 缓存串联实战。刷题建议从 LeetCode 简单题开始每天 1-2 题坚持就是胜利。