★ FEATURED ARTICLE 摘要算法和数据结构是编程能力的基础。很多性能问题并不是由语言本身造成的而是因为没有根据数据规模选择合适的数据结构或者忽略了算法的时间和空间复杂度。本文从复杂度分析开始介绍数组、动态数组和链表的基本结构、访问与插入特点并通过 Python 实现简单的数据结构和常见操作为后续学习栈、队列、树、图和排序算法建立基础。一、背景与问题同一个功能可以有不同实现。例如从一组数据中判断某个元素是否存在items[A,B,C,D]targetDprint(targetinitems)当数据量很小时不同实现之间的差异不明显当数据量达到百万甚至更大时查找、插入和删除的成本会直接影响响应时间。常见问题包括只关注代码能否运行不分析数据规模。对列表头部频繁插入和删除导致性能下降。用线性查找处理本可以使用哈希结构的数据。递归深度、内存占用和最坏情况被忽略。复杂度分析停留在术语层面没有联系实际操作。算法学习的第一步不是背诵公式而是理解数据结构如何组织数据以及每个操作需要移动、比较或访问多少元素。二、核心概念1. 时间复杂度时间复杂度描述输入规模增长时算法执行步骤如何增长。常见复杂度如下复杂度典型场景O(1)通过索引访问数组元素O(log n)有序数组二分查找O(n)遍历数组O(n log n)高效比较排序O(n²)双重循环比较所有元素复杂度通常关注增长趋势不强调常数项和低阶项。例如3n 10通常记为O(n)。2. 空间复杂度空间复杂度描述算法额外使用的内存。输入数据本身占用的空间通常不计入额外空间但复制数组、递归栈和辅助哈希表需要计入。时间和空间经常需要权衡使用更多内存建立索引 → 查询速度更快 减少额外内存 → 可能需要重复扫描数据3. 数组数组将元素存放在连续或逻辑连续的位置并通过下标访问index: 0 1 2 3 value: 10 20 30 40数组的特点按下标访问通常是O(1)。尾部追加通常成本较低。中间插入和删除需要移动元素。适合随机访问和批量遍历。4. 动态数组Python 的list是动态数组。当容量不足时运行时会申请更大的空间并复制元素。扩容策略通常让连续追加的均摊复杂度接近O(1)但单次扩容可能需要O(n)。5. 链表链表由节点组成每个节点保存数据和下一个节点的引用head │ ▼ [10 | next] → [20 | next] → [30 | None]链表不要求节点连续存储。已知节点位置时插入和删除可以只修改引用但按下标查找需要从头遍历通常是O(n)。三、工作原理1. 操作复杂度对比操作动态数组单向链表按下标访问O(1)O(n)头部插入O(n)O(1)尾部追加均摊O(1)O(n)有尾指针时可为O(1)中间插入O(n)找位置O(n)修改引用O(1)按值查找O(n)O(n)删除已知位置移动元素O(n)修改引用O(1)表格中的复杂度描述的是典型情况实际结果还会受到缓存、内存布局和实现细节影响。2. 为什么数组访问是O(1)如果数组首地址为base每个元素占用size字节那么第i个元素的地址可以近似计算为address(i) base i × size因此不需要从第一个元素逐个查找。3. 为什么链表按下标访问是O(n)单向链表只有当前节点指向下一个节点的引用。要找到第i个节点通常必须从头节点开始逐个跳转最多访问i 1个节点。4. 均摊复杂度动态数组偶尔需要扩容但大多数追加操作不需要移动已有元素。把一系列操作的总成本平均到每次操作上就得到均摊复杂度。理解均摊复杂度后可以解释为什么 Python 列表连续append通常表现良好但在头部频繁insert仍然不适合。四、实战示例1. 数组和列表操作numbers[10,20,30,40]print(numbers[2])numbers.append(50)numbers[1]25print(numbers)通过下标访问和修改不需要遍历整个列表。2. 头部操作的差异fromcollectionsimportdeque items[2,3,4]items.insert(0,1)print(items)queuedeque([2,3,4])queue.appendleft(1)print(queue)如果需要频繁从两端插入和删除deque通常比列表更合适。数据结构选择应由操作模式决定。3. 实现单向链表from__future__importannotationsfromdataclassesimportdataclassdataclassclassNode:value:intnext:Node|NoneNoneclassSinglyLinkedList:def__init__(self)-None:self.head:Node|NoneNoneself.tail:Node|NoneNoneself.size0defappend(self,value:int)-None:nodeNode(value)ifself.headisNone:self.headself.tailnodeelse:assertself.tailisnotNoneself.tail.nextnode self.tailnode self.size1defvalues(self)-list[int]:result:list[int][]currentself.headwhilecurrentisnotNone:result.append(current.value)currentcurrent.nextreturnresult保存尾指针后链表尾部追加可以避免每次从头遍历。4. 删除第一个匹配节点defremove_first(self,value:int)-bool:previous:Node|NoneNonecurrentself.headwhilecurrentisnotNone:ifcurrent.valuevalue:ifpreviousisNone:self.headcurrent.nextelse:previous.nextcurrent.nextifcurrentisself.tail:self.tailprevious self.size-1returnTruepreviouscurrent currentcurrent.nextreturnFalse查找目标节点需要O(n)找到后修改引用本身是O(1)。5. 线性查找与二分查找deflinear_search(values:list[int],target:int)-int:forindex,valueinenumerate(values):ifvaluetarget:returnindexreturn-1defbinary_search(values:list[int],target:int)-int:left,right0,len(values)-1whileleftright:middle(leftright)//2ifvalues[middle]target:returnmiddleifvalues[middle]target:leftmiddle1else:rightmiddle-1return-1二分查找要求数据已经有序。它通过每次排除一半候选区间将查找复杂度从O(n)降低到O(log n)。6. 复杂度测试fromtimeitimporttimeit valueslist(range(100_000))linear_timetimeit(lambda:linear_search(values,99_999),number100,)binary_timetimeit(lambda:binary_search(values,99_999),number100,)print(linear:,linear_time)print(binary:,binary_time)基准测试只能说明当前实现、数据和机器上的表现不能代替复杂度分析但可以帮助发现实现错误和明显的性能差异。7. 使用集合优化存在性判断allowed_users{u001,u002,u003}user_idu002ifuser_idinallowed_users:print(allowed)集合通常使用哈希结构平均情况下成员判断接近O(1)。如果只需要判断是否存在不必每次在线性列表中扫描。五、常见问题与实践建议1.O(1)是否表示一定很快不一定。复杂度描述增长趋势不代表常数开销为零。一个常数很大的O(1)操作在小数据和特定硬件上可能慢于简单的O(n)操作。2. 为什么列表中间插入较慢因为插入位置后面的元素通常需要整体向后移动为新元素腾出空间移动数量随列表长度增长。3. 什么时候使用链表链表适合需要频繁在已知节点位置插入和删除、且不依赖随机访问的场景。实际 Python 业务中很多队列场景使用deque已经足够不需要手写链表。4. 二分查找为什么返回错误结果优先检查输入是否已经按同一规则排序。left和right的边界是否一致。找到目标后是否及时返回。更新边界时是否排除了已经检查过的中间位置。5. 复杂度分析需要考虑最坏情况吗通常需要。平均复杂度有助于描述常见表现但权限、支付、任务调度等关键路径更应该关注最坏情况和资源上限。六、进阶思考1. 数据结构选择应从操作开始先列出核心操作再选择结构需要按下标随机访问 → 数组 / 动态数组 需要两端进出 → deque 需要快速判断是否存在 → set 需要键值映射 → dict 需要优先处理最小或最大元素 → heap不要因为某个结构“更高级”就使用它操作模式才是选择依据。2. 理论复杂度与实际性能真实性能还会受缓存局部性、内存分配、解释器开销、数据分布和并发影响。连续数组通常更利于缓存访问链式结构则可能因为节点分散而产生额外开销。3. 不变量实现数据结构时要为每个操作维护不变量。例如单向链表需要保证空链表的head和tail状态一致。tail.next始终为None。size与实际节点数量一致。删除最后一个节点后head和tail都正确更新。不变量比记住某段代码更重要因为它能指导边界情况处理。4. 为算法增加测试至少测试空数组或空链表。只有一个元素。目标在头部、中间和尾部。目标不存在。重复值。删除后结构为空。算法代码短并不代表边界条件少。结论算法学习的基础是理解复杂度和数据结构操作成本。数组适合随机访问链表适合已知节点位置的连接调整列表、deque、集合和字典分别对应不同的操作模式。后续可以继续学习栈与队列、哈希表、递归与回溯、树和图、排序与动态规划并在每个主题中坚持分析时间复杂度、空间复杂度和边界条件。参考资料Python 官方文档https://docs.python.org/3/CPythonlist数据结构文档https://docs.python.org/3/tutorial/datastructures.htmlIntroduction to Algorithmshttps://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
阅读完成 · 觉得有帮助？
