使用内置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
相关产品推荐
相关产品推荐

