目錄Python進階教程算法與數據結構入門一、時間復雜度二、常用數據結構2.1 列表與字典2.2 棧Stack2.3 隊列Queue三、排序算法3.1 冒泡排序O(n2)3.2 快速排序O(n log n)四、查找算法五、遞歸六、動態規劃入門七、實戰實現 LRU 緩存總結Python進階教程算法與數據結構入門本文是Python 入門教程系列的第 18 篇擴展篇。算法與數據結構是編程的內功本篇介紹最核心的幾種用 Python 實現。一、時間復雜度衡量算法效率用大 O 表示法描述執行時間隨數據規模增長的速度復雜度含義示例O(1)常數時間數組按下標訪問O(log n)對數時間二分查找O(n)線性時間遍歷列表O(n log n)線性對數快速排序O(n2)平方時間冒泡排序二、常用數據結構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(n2)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 題堅持就是勝利。