我不知道如何计算这个算法的时间复杂度,我知道嵌套循环是 O(n^2) 但我不知道如何处理 .insert(),我得出了错误的结论是 O(n^2 + n log n) 但我知道我不能在大 O 中求和,任何帮助将不胜感激。
for i in range(arr_len):
for j in range(arr_len):
if (i == arr[j]):
max_bin_heap.insert(//whatever) //O(log n)
最佳答案
乍一看,大多数人会说这是O(n*n*logn)
,因为有两个嵌套循环和O(logn)
操作 max_bin_heap.insert 在内部
。然而,事实并非如此!注意 for
循环中调用if (i == arr[j])
条件。对于内部 for
循环中的每个 j
,i
的至多一个值将等于 arr[j]
,因此两个 for
循环不会引发 n^2
次 max_bin_heap.insert 调用
,而只会引发 n
他们中的。由于有 n^2
比较和最多 n*logn
堆操作,总复杂度为 O(n*logn + n*n) = O( n^2)
.
关于algorithm - 双嵌套循环函数中 O(log n) 的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48684855/