algorithm - 双嵌套循环函数中 O(log n) 的时间复杂度

Question

我不知道如何计算这个算法的时间复杂度，我知道嵌套循环是 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)

Answer 1

乍一看，大多数人会说这是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).