第1讲: 数据结构与时间和空间复杂度场景快递分拣中心仓库里已经有1000个包裹按区域分好了。现在新来了1个包裹要确定它该放到哪个区域。方案A逐个比对邮编新来的包裹邮编是214000员工拿出仓库里已有的1000个包裹逐个看它们的邮编找到邮编相近的就知道该放哪个区最坏情况要比对1000次如果仓库有100万个包裹要比对100万次方案B按邮编直接定位提前把仓库分成100个区按邮编后两位00区、01区…99区新来的包裹邮编214000看后两位是00直接走到00区1步搞定不管仓库有1000个还是100万个包裹都是1步 关键洞察方案A的 O(n)需要遍历已有数据或规则才能确定位置。方案B的 O(1)通过某种预处理方式分区/哈希让定位变成直接计算。这和算法中的哈希表完全对应方案A 线性查找for item in list: if match: return方案B 哈希定位index hash(key) % 100→ 直接走到对应位置二、时间复杂度: 程序要跑多久?2.1 生活中的类比复杂度生活场景直观感受O(1)直接按门牌号找到你家瞬间完成, 和小区多大无关O(log n)翻电话簿找人(每次撕一半)1000页撕10次, 100万页撕20次O(n)逐个检查每个包裹1000个查1000次, 100万个查100万次O(n log n)把1000人按身高排队(快速排序)比逐个查快很多, 但比直接找慢O(n^2)1000人两两握手每个人和所有人都握手, 爆炸增长O(2^n)密码破解, 逐个试所有组合每多1位密码, 工作量翻倍, 很快天文数字2.2 图形化理解工作量 | | * O(2^n) - 爆炸增长, 很快受不了 | * | * | * O(n^2) - 二次方, 也很恐怖 | * | * | * O(n log n) - 实际常用算法大多在这里 |* |* O(n) - 线性, 还能接受 | |* O(log n) - 很优秀 | |* O(1) - 完美! ------------------------------- 数据量 n 1 10 100 1000 100002.3 代码实战: 亲眼见证速度差异打开你的Python, 复制下面的代码, 亲手运行:importtime# # 实验1: O(1) -- 直接访问, 瞬间完成# defo1_access(arr,index):直接按索引取元素, 不管数组多大都是1步returnarr[index]# 准备一个超大数组(1000万元素)big_arraylist(range(10_000_000))starttime.time()resulto1_access(big_array,5_000_000)# 取中间那个endtime.time()print(fO(1) 访问1000万数组的第500万个元素:{result})print(f耗时:{(end-start)*1000:.4f}毫秒\n)# # 实验2: O(n) -- 逐个查找, 随数据量线性增长# defon_search(arr,target):逐个查找目标值, 最坏要遍历全部fori,valinenumerate(arr):ifvaltarget:returnireturn-1starttime.time()resulton_search(big_array,9_999_999)# 找最后一个endtime.time()print(fO(n) 在1000万数组中查找最后一个: 索引{result})print(f耗时:{(end-start)*1000:.4f}毫秒\n)# # 实验3: O(n^2) -- 双重循环, 爆炸增长# defon2_find_pairs(arr):找出数组中所有和为100的数对--暴力双重循环pairs[]nlen(arr)foriinrange(n):forjinrange(i1,n):ifarr[i]arr[j]100:pairs.append((arr[i],arr[j]))returnpairs# 为了安全, 只用1000个元素测试(1000万会卡死!)small_arraylist(range(1000))starttime.time()pairson2_find_pairs(small_array)endtime.time()print(fO(n^2) 在1000数组中找和为100的数对, 找到{len(pairs)}对)print(f耗时:{(end-start)*1000:.4f}毫秒)print(注意: 如果是100万元素, 这个算法要跑几个小时!\n)# # 实验4: O(log n) -- 二分查找, 每次砍一半# defologn_binary_search(arr,target):在有序数组中二分查找, 每次排除一半left,right0,len(arr)-1steps0# 记录步数whileleftright:steps1mid(leftright)//2ifarr[mid]target:returnmid,stepselifarr[mid]target:leftmid1else:rightmid-1return-1,steps starttime.time()result,stepsologn_binary_search(big_array,9_999_999)endtime.time()print(fO(log n) 在1000万有序数组中二分查找: 索引{result})print(f只比较了{steps}次!)print(f耗时:{(end-start)*1000:.4f}毫秒\n)# # 实验5: 对比总结# print(*50)print(复杂度对比总结(处理1000万数据))print(*50)print(O(1) - 直接访问 - 瞬间完成)print(O(log n) - 二分查找 - 只需比较 ~24次)print(O(n) - 逐个查找 - 最多查1000万次)print(O(n^2) - 双重循环 - 1000万^2 100万亿次(不可能完成))print(*50)运行结果示例:O(1) 访问1000万数组的第500万个元素: 5000000 耗时: 0.0012 毫秒 O(n) 在1000万数组中查找最后一个: 索引9999999 耗时: 850.2341 毫秒 O(n^2) 在1000数组中找和为100的数对, 找到 50 对 耗时: 45.6789 毫秒 O(log n) 在1000万有序数组中二分查找: 索引9999999 只比较了 24 次! 耗时: 0.0089 毫秒关键发现: 二分查找只比较了24次就找到了1000万数据中的目标! 这就是 O(log n) 的威力。三、空间复杂度: 程序要用多少内存?3.1 生活类比空间复杂度生活场景O(1)只用1张纸记录, 不管处理多少数据O(n)给每个人发1张登记表, 1000人需要1000张O(n^2)做一张1000x1000的表格记录两两关系3.2 代码实战: 空间差异# # 实验A: O(1) 空间 -- 只用几个变量# defo1_space_sum(arr):求数组总和, 只用1个变量存储结果total0# - 只占1个空间fornuminarr:totalnumreturntotal# # 实验B: O(n) 空间 -- 额外创建同样大的数组# defon_space_copy(arr):复制一份数组, 空间翻倍copyarr[:]# - 额外占用 n 个空间returnsum(copy)# # 实验C: O(n^2) 空间 -- 创建二维表格# defon2_space_matrix(n):创建 n x n 的矩阵matrix[]foriinrange(n):row[0]*n# - 每行 n 个元素matrix.append(row)returnmatrix# 测试importsys arrlist(range(10000))# O(1) 空间print(fO(1) 空间: 只用1个变量)# O(n) 空间copyarr[:]print(fO(n) 空间: 复制数组占用{sys.getsizeof(copy)}字节)# O(n^2) 空间matrixon2_space_matrix(1000)print(fO(n^2) 空间: 1000x1000矩阵占用大量内存)四、LeetCode实战题目1: 两数之和 (LC 1)题目: 给定一个数组和一个目标值, 找出数组中和为目标值的两个数的索引。示例:输入: nums [2, 7, 11, 15], target 9 输出: [0, 1] (因为 2 7 9)暴力解法 O(n^2)deftwo_sum_brute(nums,target): 思路: 双重循环, 每两个数都试一试 时间: O(n^2) -- 两两组合 空间: O(1) -- 只用几个变量 nlen(nums)foriinrange(n):forjinrange(i1,n):ifnums[i]nums[j]target:return[i,j]return[]# 测试nums[2,7,11,15]target9print(f暴力解法:{two_sum_brute(nums,target)})问题: 如果数组有10万元素, 内层循环要跑约50亿次! 太慢了。优化解法 O(n) – 哈希表deftwo_sum_hash(nums,target): 思路: 用字典(哈希表)存储已经见过的数 时间: O(n) -- 只遍历1次 空间: O(n) -- 字典最多存n个数 核心思想: 对于每个数 num, 我只需要找 target - num 是否在之前出现过 用字典可以实现 O(1) 的查找! seen{}# key数字, value索引fori,numinenumerate(nums):complementtarget-num# 我需要找的另一个数ifcomplementinseen:# 找到了! 返回两个索引return[seen[complement],i]# 把当前数加入字典, 供后面的数查找seen[num]ireturn[]# 测试nums[2,7,11,15]target9print(f哈希表解法:{two_sum_hash(nums,target)})# # 性能对比# importtime big_numslist(range(100000))big_nums[-1]99999target9999999998# 暴力法(只测小数据)starttime.time()two_sum_brute(big_nums[:1000],1997)print(f\n暴力法(1000个元素):{(time.time()-start)*1000:.2f}ms)# 哈希表法starttime.time()two_sum_hash(big_nums,target)print(f哈希表法(10万个元素):{(time.time()-start)*1000:.2f}ms)图解哈希表解法:遍历到第0个元素: num2 - 需要找 9-27 - 字典里还没有7 - 存入: {2: 0} 遍历到第1个元素: num7 - 需要找 9-72 - 字典里有2! 索引是0 - 返回 [0, 1] 对 总共只遍历了2次, 而不是4x416次!核心思想: 用空间换时间。多花一点内存存字典, 换来从 O(n^2) 降到 O(n)。题目2: 存在重复元素 (LC 217)题目: 判断数组中是否存在重复的元素。示例:输入: [1, 2, 3, 1] 输出: True (1出现了两次) 输入: [1, 2, 3, 4] 输出: False (没有重复)解法对比: 时空复杂度的权衡defcontains_duplicate_sort(nums): 方法A: 先排序, 再检查相邻元素 时间: O(n log n) -- 排序的代价 空间: O(1) 或 O(log n) -- 取决于排序算法 nums.sort()# 原地排序foriinrange(len(nums)-1):ifnums[i]nums[i1]:returnTruereturnFalsedefcontains_duplicate_set(nums): 方法B: 用集合去重 时间: O(n) -- 遍历一次 空间: O(n) -- 集合最多存n个数 seenset()fornuminnums:ifnuminseen:returnTrueseen.add(num)returnFalsedefcontains_duplicate_pythonic(nums): 方法C: Python一行解法 时间: O(n) -- 创建集合 空间: O(n) -- 集合 returnlen(nums)!len(set(nums))# # 测试与对比# test_cases[[1,2,3,1],# True[1,2,3,4],# False[1,1,1,3,3],# True]fornumsintest_cases:print(f\n数组:{nums})print(f 排序法:{contains_duplicate_sort(nums.copy())})print(f 集合法:{contains_duplicate_set(nums)})print(f 一行法:{contains_duplicate_pythonic(nums)})# # 时空复杂度权衡分析# print(\n*50)print(两种方法的权衡)print(*50)print( 方法A(排序): 优点: 空间占用小, 原地修改 缺点: O(n log n) 时间, 会修改原数组 方法B/C(集合): 优点: O(n) 时间, 更快 缺点: O(n) 额外空间 面试时通常优先选方法B, 因为时间更宝贵。 但如果题目要求不使用额外空间, 就必须用方法A。 )五、大O表示法的核心规则5.1 只看最坏情况deffind_first_even(nums):找第一个偶数fornuminnums:ifnum%20:returnnum# 可能第1个就找到returnNone问题: 这个函数是 O(1) 还是 O(n)?答案:O(n)! 因为大O看的是最坏情况。最好情况: 第1个就是偶数 - O(1)最坏情况: 全是奇数, 遍历完 - O(n)大O表示法:取最坏情况 O(n)5.2 只保留增长最快的项defcomplex_function(n): 这个函数的时间复杂度是多少? # 第1步: O(1)x1# 第2步: O(n)foriinrange(n):print(i)# 第3步: O(n^2)foriinrange(n):forjinrange(n):print(i,j)# 第4步: O(n)forkinrange(n):xk# 总复杂度 O(1) O(n) O(n^2) O(n)# O(n^2) - 只保留最大的项!规则:O(2n) O(n) – 常数系数忽略O(n^2 n) O(n^2) – 低阶项忽略O(n^2 1000000) O(n^2) – 常数项忽略5.3 常见复杂度速查表复杂度名称能处理的数据量例子O(1)常数无限大数组索引访问O(log n)对数极大(10亿只需30步)二分查找O(n)线性千万级遍历数组O(n log n)线性对数百万级快速排序、归并排序O(n^2)平方万级双重循环O(2^n)指数20-30穷举所有子集O(n!)阶乘10-12全排列六、动手练习练习1: 判断复杂度看看下面的代码, 判断时间复杂度:# 代码Adeffunc_a(n):foriinrange(n):print(i)# 答案: _____# 代码Bdeffunc_b(n):foriinrange(n):forjinrange(n):print(i,j)# 答案: _____# 代码Cdeffunc_c(n):i1whilein:print(i)i*2# 答案: _____# 代码Ddeffunc_d(n):print(hello)# 答案: _____答案:代码A: O(n) – 循环n次代码B: O(n^2) – 双重循环代码C: O(log n) – i每次翻倍, 循环 log2(n) 次代码D: O(1) – 固定操作, 与n无关练习2: 优化下面的代码deffind_common(arr1,arr2): 找出两个数组的公共元素 当前是 O(n x m), 请优化到 O(nm) result[]forainarr1:# n次forbinarr2:# m次ifab:result.append(a)returnresult# 请在这里写出优化后的代码:答案:deffind_common_optimized(arr1,arr2): 用集合实现 O(nm) set1set(arr1)# O(n)result[]forbinarr2:# O(m)ifbinset1:# O(1) -- 集合查找是常数时间!result.append(b)returnresult七、本讲总结核心要点时间复杂度 程序运行时间随数据量增长的速度空间复杂度 程序占用内存随数据量增长的速度大O表示法只看最坏情况, 忽略常数和低阶项O(1) O(log n) O(n) O(n log n) O(n^2) O(2^n)常见优化策略: 用哈希表把 O(n^2) - O(n), 用二分把 O(n) - O(log n)面试高频问题问题答案数组访问的时间复杂度?O(1)链表查找的时间复杂度?O(n)二分查找的时间复杂度?O(log n)快速排序的时间复杂度?平均 O(n log n), 最坏 O(n^2)哈希表查找的时间复杂度?平均 O(1), 最坏 O(n)下节预告第2讲: 数组– 从内存角度理解数组为什么能 O(1) 访问, 以及前缀和、差分数组等实战技巧。课后作业:把本讲所有代码亲手跑一遍去 LeetCode 做 LC 1. 两数之和 和 LC 217. 存在重复元素尝试用哈希表优化的思路, 思考如何把 O(n^2) 的问题降到 O(n)