c - 内循环的运行时间是多少？

Question

我做了一个函数，它循环遍历数组并打印数组中可以加起来为值 K 的任意两个值。外层的 for 循环是 O(n)，但内层循环让我有点困惑，如果运行时间是 O(Log n) 或 O(n)。你能帮忙吗？谢谢!!

int canMakeSum(int *array, int n, int key){
  int i, j;

  for(i = 0; i < n; i++){
    for(j = (i+1); j < n; j++){
      if(array[i]+array[j] == key){
        printf("%d + %d = %d\n", array[i], array[j], key);
      }
    }
  }
}

Answer 1

正如其他人已经展示的那样，内部循环仍然是O(n)；它是 n/2 次迭代的平均值，值 1 到 n 均匀分布在外循环的迭代中。

是的，你可以在O(n log n)中解决这个问题。

首先对数组进行排序；这是 n log n。现在，您有一个查找所有组合的线性 (O(n)) 过程。

lo = 0
hi = n-1

while lo < hi {
   sum = array[lo] + array[hi]
   if sum == k {
       print "Success", array[lo], array[hi]
       lo += 1
       hi -= 1
   }
   else if sum < k        // need to increase total
       lo += 1
   else                   // need to decrease total
       hi -= 1