如果我有两个 for 循环，一个循环一个常量值，另一个循环遍历数组大小 M，那么时间复杂度是 O(M) 还是 O(kM)？

Question

我写了一个代码来回答这个问题：

给定一个整数数组 nums 和一个整数 k，return k 个出现频率最高的元素。您可以 return 以任何顺序回答。

示例 1：输入：nums = [1,1,1,2,2,3], k = 2 输出：[1,2]

为了总结我的代码，我将 nums 中的每个项目作为键输入到我的字典中，然后通过遍历 nums 简单地对每个元素进行计数，并将对象的 'count' 作为值存储在词典：

from collections import defaultdict

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:

        my_dict = defaultdict(int)
        top_two_final = []

        for i in range(len(nums)):
            my_dict[nums[i]] += 1

        sorted_values = sorted(my_dict.values(), reverse=True)

        for j in my_dict:
            for l in sorted_values[:k]:
                if my_dict[j] == l:
                    top_two_final.append(j)

        return set(top_two_final)

我的问题是关于时间和 SPACE 复杂性。

我相信两者都是O(Mk)；其中 M 是输入 nums 的大小，数组“sorted_values”（即 k）的大小

但由于 k 是常数，是否可以得出两个复杂度均为 O(M) 的结论？

Answer 1

它似乎只是 在最好的情况下 O(M)。 在最坏的情况下 当 nums 列表是连续的数字 [1,2,3...M] 时，大 O 变为 O(MlogM) 由于排序。

如果我有两个 for 循环，一个循环一个常量值，另一个循环遍历数组大小 M，那么时间复杂度是 O(M) 还是 O(kM)？

if I have two for loops and one loops a constant value and the other iterates over array size M, is the time complexity O(M) or O(kM)?

python

time-complexity