双嵌套循环函数中 O(log n) 的时间复杂度
Time complexity of O(log n) in double nested loop function
我不知道如何计算这个算法的时间复杂度，我知道嵌套循环是 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)内层for循环中的max_bin_heap.insert call操作。然而，事实并非如此！注意 if (i == arr[j]) 条件。对于来自内部 for 循环的每个 j，最多 i 的一个值将等于 arr[j]，因此两个 for 循环不会导致 [= max_bin_heap.insert call 的 20=] 次调用，但只有 n 次调用。由于有n^2次比较，最多n*logn次堆操作，总复杂度为O(n*logn + n*n) = O(n^2).
我不知道如何计算这个算法的时间复杂度，我知道嵌套循环是 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)内层for循环中的max_bin_heap.insert call操作。然而，事实并非如此！注意 if (i == arr[j]) 条件。对于来自内部 for 循环的每个 j，最多 i 的一个值将等于 arr[j]，因此两个 for 循环不会导致 [= max_bin_heap.insert call 的 20=] 次调用，但只有 n 次调用。由于有n^2次比较，最多n*logn次堆操作，总复杂度为O(n*logn + n*n) = O(n^2).