You need to enable JavaScript to run this app. 使用内置sorted函数的find_missing函数的时间复杂度是多少?
优惠活动
大模型
产品
解决方案
定价
更多

使用内置sorted函数的find_missing函数的时间复杂度是多少?

时间复杂度分析
  • 内置sorted函数的时间复杂度:Python 内置排序采用 Timsort 算法,平均和最坏时间复杂度均为 O(n log n),其中 n 是输入列表 num_array 的元素个数。
  • 后续的遍历循环最坏情况下会遍历所有相邻元素对,时间复杂度为 O(n)。
  • 时间复杂度计算取最高阶增长项,低阶项可直接忽略,因此整个 find_missing 函数的时间复杂度为 O(n log n)。

补充说明

针对你当前的使用场景(取值固定为1到99的列表,仅缺失1个值),存在更优实现方案:1到99的固定和为4950,直接用4950减去输入列表所有元素的和即可得到缺失值,该方案时间复杂度仅为 O(n),不需要额外排序操作。
另外你当前的代码存在边界缺陷:如果缺失值是1或者99,遍历结束后没有匹配的判断条件,函数会直接返回None,无法得到正确结果。

内容的提问来源于stack exchange,提问作者Michał Dramiński

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.18 05:45:08