双嵌套循环函数中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 callforif (i == arr[j])jforiarr[j]forn^2max_bin_heap.insert callnn^2n*lognO(n*logn + n*n) = O(n^2)