Каково время выполнения внутреннего цикла?

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).Общая временная сложность O (n ^ 2).

Представьте, что у вас есть массив из 25000 элементов.В начальной точке в i = 0 и j = 1 число элементов, через которые j будет проходить итерация (в худшем случае нет совпадений с ключом), составляет 24999 элементов.Что является небольшим отличием от общего количества элементов, так что это «похоже» на прохождение n элементов.

Answer 2

Как уже показали другие, внутренний цикл по-прежнему 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

Answer 3

Поскольку внутренние циклы зависят от значения внешнего цикла, вы не можете найти сложность всей программы, не проанализировав оба вместе.Сложность внутреннего цикла составляет n - i - 1.

Если вы хотите вычислить сложность программы, вы можете сложить сумму от n - i -1 от i = 0 до i = n - 1.Следовательно, общая сложность равна T(n) = (n - 1) + (n-2) + ... + 1 + 0 = (n-1)n/2 = \Theta(n^2) (так как разметка во внутреннем цикле имеет постоянную сложность (\Theta(1))).