Python代码片段大O时间复杂度判定及实用技巧咨询

代码1：实际复杂度与你的初步判断一致，为O(len(n)) #

逐行拆解运行逻辑：

• 入参n是类序列对象（代码中调用了len(n)），外层循环一共执行len(n)次
• 初始值k=0，代码里k += 1的位置在整个for循环的外部，意味着for循环执行的全流程中，k的值始终为0，内层循环for j in range(0, k)每次进入时都是range(0,0)，没有任何一次实际执行
• 全程操作数和入参序列长度线性相关，整体复杂度为O(n)（此处的n指代输入序列的长度），你最初的判断是正确的。只是要注意这段代码的缩进逻辑存在问题，原本想实现的k累计效果根本没有生效。

代码2：实际复杂度为O(log n) #

这段bar函数是标准的递归实现二分查找：

• 运行前提是输入的x为有序序列，每次调用都会通过取中间值的方式，将待搜索的区间长度直接砍半
• 无论是否找到目标值，最多需要log2(初始列表长度)次递归就会到达边界退出，没有其他额外循环操作，整体属于对数级复杂度O(log n)，是查找类操作中效率极高的实现。

代码3：你的初步判断存在偏差，默认场景下复杂度为O(m*n) #

• 外层循环遍历长度为m的序列a，一共执行m次的逻辑判断是正确的
• 但循环内部的char in b操作耗时和b的类型强相关：如果b是列表、元组这类顺序存储的普通序列，in操作最坏需要从头到尾遍历完长度为n的b才能确认字符存在/不存在，这一步单次就需要花O(n)的时间
• 整体下来就是m次循环 × 单次O(n)的查找耗时，即O(m*n)。只有提前把b转成set、dict这类哈希结构，让in操作变成O(1)的恒定耗时，整体复杂度才能降到O(m)。

• 不要看到嵌套循环就直接套用O(n²)的结论，顺着每层循环的变量范围计算实际执行次数：有的内层循环变量初始值为0、或者累计逻辑因缩进错位根本没执行，实际耗时远低于直观的嵌套次数估算。
• 重点记牢Python常见内置操作的固定复杂度：比如列表的下标读取是O(1)，in操作对列表/元组是O(n)，对set/dict是O(1)，字符串的拼接、切片耗时和操作长度线性相关，这些隐藏的耗时是初学者最容易漏算的部分。
• 碰到递归代码，先看每次递归把原始问题的规模缩小了多少：每次规模砍一半就是O(log n)，每次规模减1就是O(n)，每次拆成多个同规模子问题就是更高阶的指数级、多项式级复杂度。
• 大O本身是粗粒度的量级描述，判定时只需要保留增长速度最快的项，忽略常数和低阶项：比如总操作数是3*n + 100就归为O(n)，总操作数是n² + 1000*n就归为O(n²)，不需要被零散的固定操作数干扰判断。

内容的提问来源于stack exchange，提问作者starglitter