Как рассчитать анализ наихудшего случая по этому алгоритму?

Question

sum = 0;
for(int i = 0; i < N; i++)
    for(int j = i; j >= 0; j--)
       sum++;

Насколько я понимаю, первая строка - это 1 операция, 2-я строка - (i+1) операций, 3-я строка - (i-1) операций и 4-я строка - n операций.Означает ли это, что время работы будет 1 + (i+1)(i-1) + n?Именно эти последние шаги меня смущают.

Answer 1

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

Чтобы проанализировать алгоритм, подобный этому, попробуйте определить некоторую величину, значение которой находится в постоянном множителе общего времени выполнения алгоритма. В этом случае эта величина, вероятно, будет равна «сколько раз строка sum++ выполняется?», Так как, если мы знаем это значение, мы знаем общее количество времени, потраченное двумя циклами в алгоритме. Чтобы понять это, давайте проследим, что происходит с этими циклами. На первой итерации внешнего цикла i == 0 и внутренний цикл будет выполняться ровно один раз (с 0 по 0). На второй итерации внешнего цикла i == 1 и внутренний цикл выполняется ровно дважды (сначала с j == 1, один раз с j == 0. В более общем смысле, на k-й итерации внешнего цикла внутренний цикл выполняет k + 1 Это означает, что общее число итераций самого внутреннего цикла определяется как

1 + 2 + 3 + ... + N

Эта величина может быть показана равной

N (N + 1)      N^2 + N    N^2    N
---------   =  ------- =  --- + ---
    2             2        2     2

Из этих двух терминов термин N^2 / 2 является доминирующим термином роста, и поэтому, если мы игнорируем его постоянные факторы, мы получаем время выполнения O (N ² ).

Не смотрите на этот ответ как на то, что вы должны запомнить - подумайте обо всех шагах, необходимых для получения ответа. Мы начали с поиска некоторой величины для подсчета, а затем увидели, как на эту величину повлияло выполнение циклов. Из этого мы смогли вывести математическое выражение для этой величины, которое затем упростили. Наконец, мы взяли результирующее выражение и определили доминантный термин, который служит в качестве big-O для всей функции.

Answer 2

Работа изнутри.

sum++

Это отдельная операция, которая не повторяется.

for(int j = i; j >= 0; j--)

Это циклы я + 1 раз. Там есть несколько операций, но вы, вероятно, не хотите считать количество asm-инструкций. Поэтому я предполагаю, что для этого вопроса это множитель i + 1. Поскольку содержимое цикла является отдельной операцией, цикл и его блок выполняют операции i + 1.

for(int i = 0; i < N; i++)

Это повторяется N раз. Как и прежде, это множитель N. Поскольку блок выполняет операции i + 1, этот цикл выполняет всего N (N + 1) / 2 операций. И это твой ответ! Если вы хотите рассмотреть сложность big-O, то это упрощается до O (N ² ).

Answer 3

Это не аддитивно: внутренний цикл происходит один раз для КАЖДОЙ итерации внешнего цикла.Так что это O (n ² ).

Кстати, это хороший пример того, почему мы используем асимптотические обозначения для такого рода вещей - в зависимости от определения «операции»точные детали подсчета могут варьироваться довольно широко.(Например, sum++ - это отдельная операция или add sum to 1 giving temp; load temp to sum?). Но поскольку мы знаем, что все, что можно скрыть в постоянном множителе, все равно будет O (n ² ).

Answer 4

Использование сигма-нотации для представления ваших циклов:

Answer 5

Итак, угадайте, что вас интересует сумма ++ и сколько раз вы ее выполняете.

Окончательный показатель суммы даст вам этот ответ.

На самом деле ваш цикл просто:

Сигма (n) n идет от 1 до N.

Что равняется: N*(N+1) / 2 Это дает вам в большой нотации O(N^2)

Кроме имени вашего вопроса, в вашем алгоритме нет худшего случая. Или вы можете сказать, что наихудший случай, когда N уходит в бесконечность.

Answer 6

Нет;Вы не учитываете определенное количество операций для каждой строки, а затем складываете их.Весь смысл таких конструкций, как 'for', состоит в том, чтобы сделать возможным выполнение данной строки кода более одного раза.Предполагается, что вы должны использовать навыки мышления и логики, чтобы выяснить, сколько раз строка 'sum ++' будет работать, как функция N. Подсказка: она запускается один раз для каждого случая, когда встречается третья строка.* Сколько раз встречается вторая строка?

Каждый раз, когда встречается вторая строка , устанавливается значение 'i'.Сколько раз третья строка запускается с этим значением i ?Поэтому сколько раз он будет работать в целом?(Подсказка: если я несколько раз дам вам другую сумму денег, как вы узнаете общую сумму, которую я вам дал?)

Каждый раз, когда встречается третья строка, четвертая строка встречается один раз.

Какая строка встречается чаще всего?Как часто это происходит, с точки зрения N?