关于求有序数组中第k小素数分数算法的时间复杂度疑问

你给出的这段Python代码用于求解有序数组中第k小的素数分数，你判断它的时间复杂度是O(n² + nlogn)，理由是嵌套for循环复杂度为O(n²)，sorted()函数复杂度为O(nlogn)且未嵌套在循环中——这个判断不正确。

代码回顾 #

from collections import defaultdict
from typing import List

def kthSmallestPrimeFraction(arr: List[int], k: int) -> List[int]:
    dictionary = defaultdict(list)
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            dictionary[arr[i] / arr[j]] = [arr[i], arr[j]]
    sorted_results = sorted(dictionary.keys())
    # return dictionary.get(sorted_results[k-1])
    return dictionary[sorted_results[k - 1]]

错误原因分析 #

• 嵌套循环部分：当数组长度为n时，i遍历从0到n-1，每个i对应的j从i+1到n-1，总共生成的分数数量是n*(n-1)/2，这部分确实是O(n²)的时间复杂度。
• 排序部分：你错误地将sorted()处理的元素数量当成了n，但实际上字典里的键数量是O(n²)级别的（也就是n*(n-1)/2个）。排序m个元素的时间复杂度是O(m logm)，这里m = n²，所以排序的时间复杂度是O(n² log(n²))，化简后为O(n² logn)。

正确的时间复杂度 #

把两部分复杂度相加，O(n²) + O(n² logn)，根据时间复杂度的渐近表示法，高阶项主导整体复杂度，所以最终时间复杂度是O(n² logn)。

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