Python算法求第n小元素的Big-O时间复杂度相关疑问

1. 示例代码的时间复杂度分析 #

你给出的这段代码并不满足O(n)线性时间复杂度要求，实际时间复杂度为O(nth * m)，其中m是输入numbers列表的长度：

• 首先你判断的没错，Python内置的min()方法需要遍历整个列表取最小值，本身时间复杂度就是O(m)；除此之外列表的remove()方法同样需要遍历列表找到目标元素、再移动后续元素完成删除，时间复杂度也是O(m)。
• 外层循环一共执行nth次，每次循环包含两次O(m)级别的操作，因此整体时间复杂度为O(nth * m)。如果nth和列表长度m是同量级（比如要找长度为1000的列表的第500小值），整体复杂度会达到O(m²)，远高于你要求的线性复杂度。

额外提醒：你贴出的示例代码还有语法错误，Python函数体内的代码需要正确缩进才能运行。

2. 新增非嵌套循环的复杂度影响 #

只要新增的循环没有嵌套在原有循环内部，且每轮循环执行的都是常量级操作，算法整体依然可以保持线性时间复杂度：

• Big O时间复杂度计算只会保留最高阶的主导项，所有常量系数、低阶项都会被忽略。比如原有操作复杂度是O(m)，新增一个遍历全列表的非嵌套循环，整体复杂度为O(m) + O(m) = O(2m)，忽略常量系数2之后依然是O(m)。就算每轮循环多执行2-3个常量操作，也只会改变常量系数的大小，不会拉高复杂度的量级。

补充参考：线性时间找第k小值的实现思路 #

如果要实现严格线性时间的第n小值查找，可以使用快速选择（Quickselect）算法，平均时间复杂度为O(n)，通过中位数选取pivot优化后可以做到最坏情况O(n)，远优于你找到的示例代码。

内容的提问来源于stack exchange，提问作者Кафка