找到最大 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]))

我不太确定这段代码的时间复杂度。任务是 return 来自未排序整数数组的最大 k 个数字。数组中的每个数字都在 [0, 10000) 范围内。我的目标是有一个明显的解决方案 max_k_sort(k, nums) 以 O(n*log(n)) 时间复杂度完成任务，另一种方法 max_k(k, nums) 完成O(n) 时间复杂度的任务，其中 n 是传递的整数数量，k 是要查找的最大值的数量。我不禁想知道是否有办法 return 以 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]

您正在执行 O(k) 操作 n 次，因此您的第二个函数的复杂度为 O(n*k)。

假设您想要按排序顺序输出，这可以通过创建一个 k 大小的堆并推送所有内容在 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) 中完成。 There exist algorithms (and python implementations) 在线性时间内找到数组中第 k 个最大的元素；很容易看出，再通过数组一次就可以构建一个包含所有数字 k 和更大数字的数组，从而给出整体 O(n).

Answer 2

Pythonstates列表排序的列表操作时间复杂度为O(N log N)。

切片是 O(k)

所以：

def max_k(k, nums):
    nums.sort(reverse=True)
    return nums[0:k]

O(k) + O(n log n) 是 O(n log n) 其中 O(k) 小于 O(n log n)

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

作为实际问题，尝试为它们计时：

import heapq
def max_k1(k, nums):
    nums.sort(reverse=True)
    return nums[0:k]

def max_k2(k, nums):
    return heapq.nlargest(k, nums)    

if __name__ == '__main__':
    import timeit
    for f in (max_k1, max_k2):
        li=[2, 8, 4, 9, 0, 12, 12, 6, 5]
        print f.__name__, timeit.timeit('f(5, li)', setup='from __main__ import f, li')

打印：

max_k1 0.240165948868
max_k2 4.96488595009

所以排序和切片比 heapq 快 20 倍。

基于评论：

import heapq
def max_k1(k, nums):
    nums.sort(reverse=True)
    return nums[0:k]

def max_k2(k, nums):
    return heapq.nlargest(k, nums)   

def max_k3(k, nums):
    return sorted(nums, reverse=True)[0:k]    

if __name__ == '__main__':
    import timeit
    for f in (max_k1, max_k2, max_k3):
        li=[2, 8, 4, 9, 0, 12, 12, 6, 5]
        print f.__name__, timeit.timeit('f(5, li)', setup='from __main__ import f, li')    

max_k1 0.242296934128
max_k2 4.52635192871
max_k3 0.332237005234

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

What is the Time Complexity of finding the max k integers?

python

algorithm

big-o

dictionary

time-complexity