Анализ времени выполнения на вложенном цикле for - PullRequest
Новая
       17

Анализ времени выполнения на вложенном цикле for

0 голосов
/ 05 октября 2019

Я пытаюсь найти время выполнения в каждой строке, когда произойдет наилучший и наихудший случай, а Big-O - в худшем и лучшем случае.

Код, который я вставил, находит самую длинную длину последовательности возрастающих чисел в массиве.

Например, если бы у нас было [4,5,6,9,1,2,3,4,5,6], самая длинная последовательность была бы 6.

будет первой дляцикл будет выполнен n раз?
будет ли второй цикл for выполняться n раз?
будет ли оператор if выполняться n раз?
Будет ли инструкция внутри if выполнена n раз?

Будет ли наилучший случай, когда массив находится в порядке возрастания, а худший - когда массив находится в порядке убывания?


Причина, по которой я не верю, что это правда, заключается в том, что при сортировке в порядке возрастания второй цикл будет проходить до конца. При сортировке в порядке убывания второй цикл всегда прерывается, поскольку оператор and не выполняется. 

for (i = 0, length = 1; i < n-1; i++) {
  for (i1 = i2 = k = i; k < n-1 && a[k] < a[k+1]; k++, i2++);
  if (length < i2 - i1 + 1)
    length = i2 - i1 + 1;
}
return length;

1 Ответ

0 голосов
/ 05 октября 2019

Во-первых, обратите внимание, что переменные i1 и i2 на самом деле не нужны, как i1 == i и i2 == k на каждой итерации внутреннего цикла, поэтому мы можем просто написать: 

for (i = 0, length = 1; i < n-1; i++) {
  for (k = i; k < n-1 && a[k] < a[k+1]; k++);
  if (length < k - i + 1)
    length = k - i + 1;
}
return length;

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

Наилучший случай имеет место, когда a - это последовательность без увеличенияВ этом случае a[k] < a[k+1] никогда не будет истинным, и, следовательно, условие внутреннего цикла будет выполнено только один раз. В этом случае возвращаемое значение будет равно 1, а сложность по времени O (n) .

Наихудший случай возникает, когда a является постоянно возрастающей последовательностью. В этом случае a[k] < a[k+1] всегда будет истинным, и, таким образом, условие внутреннего цикла будет повторяться n-1 - i раз, условие цикла еще раз, когда k < n-1 ложно.

Условие if и корректировка length выполняются в постоянное время.

Тело вложенного цикла (if) выполняется в общей сложности столько раз, сколько можно сделать multiset из 2 элементов (представленных i и k) из набора n-1 элементов. Формула для этого есть (n-1) n / 2, которая равна O (n²) .

...