Блог

Главная - Вопросы по программированию - Временная сложность второго вложенного цикла составляет всего половину

Временная сложность второго вложенного цикла составляет всего половину

#java #time-complexity

Вопрос:

У меня есть следующий код. Время выполнения кода , как я вижу, составляет O(n^2) по мере его выполнения 1, ..., n-1 , поэтому их сумма равна O(n^2). Я понял, что время выполнения действительно (n-1)(n/2), поэтому внутренние циклы выполняются от 1 до n/2, но, как я вижу, оно выполняется от 1 до n-1. Не могли бы вы, пожалуйста, показать, почему внутренний цикл выполняется не более (n/2) раз?

 public static void method2(int[] array, int n)
{
  for (int index = 1; index <= n - 1; index  ){
    privateMethod2(array[index], array, 0, index - 1);
  } // end method2
public static void privateMethod2(int entry, int[] array, int begin, int end)
{
  int index;
  for (index = end; (index >= begin) amp;amp; (entry < array[index]); index--){
    array[index   1] = array[index];
    array[index   1] = entry;
} // end privateMethod2

Ответ №1:

В худшем случае внутренний цикл выполняется в среднем n/2 раза. На первой итерации он выполняется только один раз от индекса 0 до индекса 0, на второй итерации он выполняется 2 раза от индекса=1 до индекса =0, а на последней итерации он выполняется n раз. Таким образом, в среднем он выполняется n/2 раза

Комментарии:

1. Спасибо вам за ответ. Итак, это sum(1 2 ... n) = n^2 и не n/2 так, как я это понимаю? Вопрос задан в худшем случае, хотя и не в среднем случае, хотя ответ, как кажется, является средним случаем. Как вы рассчитали это в среднем, пожалуйста? Амортизированный анализ?

2. Внутренний цикл в наихудшем случае выполняется: (1 2 3 .. n) раз, и внешний цикл выполняется n раз. Для вычисления сложности вы должны выполнить n*(n/2), потому что в худшем случае внутренний цикл выполняется в среднем n/2 раза

3. Спасибо, но на самом деле до сих пор не понял, почему внутренний цикл в худшем случае запускается n/2

4. Потому что на первой итерации он выполняется 1 раз, затем 2 раза, затем 3, а на последней итерации он выполняется n раз в худшем случае. Так что в худшем случае он в среднем выполняет n/2 итерации.

5. Как я понимаю, для каждой итерации внешнего цикла у нас будет не более n-1 во внутреннем цикле, поэтому очевидно, что это так n(n-1) . Я не в состоянии понять это альтернативно, как вы сказали. В любом случае, спасибо

Метки: