Python函数时间复杂度
我想知道我是否使用下面的函数正确计算时间复杂度。
mat 是列表的列表。
k是整数。
def kWeakestRows(mat, k):
hashmap = {}
for i in range(len(mat)):
hashmap[i] = Counter(mat[i]).get(1)
if hashmap[i] == None:
hashmap[i] = 0
result = []
while len(result) < k:
key = min(hashmap, key=hashmap.get)
result.append(key)
hashmap.pop(key)
return result
我的想法是，因为它迭代了一个 for 循环（对于列表的大小）和一个 while 循环（对于 k 的值），所以它是 O(N) 。但是在for循环中，我使用Counter来计算内部列表中的1，这将是O(N*M)。
另外，我对空间复杂度的猜测也是 O(N)，因为它用给定列表 (mat) 中的元素填充哈希图，并通过 k 的值填充列表（结果）。
如果我错了，请告诉我。
I am wondering if I calculate the time complexity correctly with the function below.
mat is a list of lists.
k is an integer.
def kWeakestRows(mat, k):
hashmap = {}
for i in range(len(mat)):
hashmap[i] = Counter(mat[i]).get(1)
if hashmap[i] == None:
hashmap[i] = 0
result = []
while len(result) < k:
key = min(hashmap, key=hashmap.get)
result.append(key)
hashmap.pop(key)
return result
My thought is since it iterates through one for loop (for size of a list) and one while loop (for the value of k), it is O(N). But in the for loop, I use Counter to count the 1s in the inner list, it would be O(N*M).
In addition, my guess on space complexity is also O(N) as it fills the hashmap with the elements in the given list (mat), and it fills a list (result) by the value of k.
Please let me know if I am wrong.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
是的！您的假设在时间和空间复杂度方面都是正确的，for 循环首先迭代直到“mat”末尾，显然是 O(N) ，而 while 循环根据长度“结果”-列表进行，因为不会存在任何类型的嵌套循环，所以它不会超出 O(N)。并且考虑到计数器功能，时间复杂度会增加。检查，所以它是 O(N*M)。此外，由于空间复杂度，我们使用的唯一内存部分是 hashmap dict，它在 for 循环中附加 0 和 mat 本身的最小值，因此在最坏情况下它本身也是 O(N) 的。
Yes! What you have assumed is correct in terms of both time and space complexity , the for loop at first iterating till end of the "mat" and it is obviously O(N) and while loop goes in accordance of length "result"- list, since there won't exist any kind of nested loops it doesn't go beyond O(N). And to take counter function into account the time complexity would increase in terms of the no. of checks, so it is of O(N*M). Also with space complexity the only memory part that we using is hashmap dict which get appended with 0 in for loop and minimum value of mat itself ,so it is also of O(N) at worst case itself.