找到最大k个整数的时间复杂度是多少？

Question

def max_k_sort(k, nums):
    # sort nums first using timsort
    # add O(n*log(n)) time complexity
    sorted_nums = sorted(nums)

    return sorted_nums[-1*k:len(nums)]

def max_k(k, nums):
    # build initial max number list
    max_nums = {}

    # add O(k) time complexity?
    i = 0
    while i < k:
        max_nums[i] = 0
        i += 1

    # add O(n) time complexity?
    least_max_key = min(max_nums, key=max_nums.get)
    least_max = max_nums[least_max_key]

    # add O(n) time complexity?
    for n in nums:
        if n > least_max:
            max_nums[least_max_key] = n
            least_max_key = min(max_nums, key=max_nums.get)
            least_max = max_nums[least_max_key]

    return max_nums.values()

print(max_k(5, [2, 8, 4, 9, 0, 12, 12, 6, 5]))

我不太确定这段代码的时间复杂性.任务是从未排序的整数数组返回最大k数.数组中的每个数字都在[0,10000)范围内.我的目标是有一个明显的解决方案max_k_sort(k,nums)以O(n*log(n))时间复杂度完成任务,另一个方法max_k(k,nums)以O(n)时间复杂度完成任务其中n是传递的整数数,k是要查找的最大值数.我不禁想知道是否有办法返回以O(n)时间复杂度排序的最大值.

Answer 1

for n in nums:
        if n > least_max:
            max_nums[least_max_key] = n
            least_max_key = min(max_nums, key=max_nums.get) # this is O(k)
            least_max = max_nums[least_max_key]

你进行了n次O(k)操作,所以你的第二个函数的复杂度是O(n*k).

假设您希望输出按排序顺序,这可以通过创建一个k -sized堆并将所有内容推送到O(n*log(k))来最容易地完成.这是为你实现的heapq.nlargest.

import heapq

heapq.nlargest(5, [2, 8, 4, 9, 0, 12, 12, 6, 5])
Out[4]: [12, 12, 9, 8, 6]

如果您不希望输出按排序顺序,则技术上可以在O(n)中完成. 存在算法(和python 实现)以在线性时间内找到数组中的第k个最大元素; 很容易看出,再一次通过数组将允许你构建一个所有数字k和更大的数组,给出整体O(n).