Как сделать это вложенным для сложности цикла?

Question

Я пытаюсь понять сложность этого времени:

for(i=0; i<=(n/2)-1; i++){
    for (j=i+1; j<=(n/2)-1; j++){
        --some O(1) thing--                
    }   
} 

Я понимаю, что внешний цикл сам по себе O (n / 2). Однако с внутренним циклом я тоже могу 'обернуть мой мозг вокруг того, как разбить, сколько раз выполняется O (1).

Если бы внутренний смотрел j = 0, я мог бы сделать n / 2 (внутренний) * n / 2 (внешний) = O(п ^ 2) сложность времени верно? Однако, поскольку j зависит от i, я думаю, что с i + 1 до n / 2 используется какой-то тип суммирования, но я не могу понять, как его настроить ...

В основном мне нужна помощьвид визуализации, сколько раз он повторяется, и как настроить суммирование. Спасибо! :)

Answer 1

Помещение

Для простоты назовем m = n / 2 - 1. Внешний цикл работает от 0 до m. Внутренний цикл от i + 1 до m.

---

Подсчет итераций

Нам нужно посчитать, как часто выполняется внутренний оператор, который вы пометили O(1). То есть как часто внутренний цикл выполняется в целом, как выполняется внешним циклом. Итак, давайте посмотрим.

Первая итерация внешнего цикла генерирует m - 1 итераций внутреннего цикла. Второй генерирует m - 1, затем m - 2, m - 3, m - 4, ..., 2, 1, 0.

Это означает, что оператор O(1)всего выполняется:

(m - 1) + (m - 2) + (m - 3) + ... + 2 + 1 + 0

Это сумма от 0 до m - 1

sum_{i = 0}^{m - 1} i

, которая может быть упрощена до

(m^2 - m) / 2

---

Заменить обратно

Давайте теперь подставим обратно m = n / 2 - 1, получим

((n / 2 - 1)^2 - (n / 2 - 1)) / 2

После упрощения это

n^2/8 - 3n/4 + 1

---

Big-O

Для Big-O мы наблюдаем, что оно меньше

  n^2 - 0 + n^2
= 2n^2

Что по определению равно O(n^2).

Как видите, этопереплет тоже туго. Таким образом, мы также получаем Omega(n^2), который также заключает Theta(n^2).

Answer 2

Предполагая, что m = n / 2. Вы увидите, что во внутреннем цикле j будет повторяться в диапазоне m-1, m-2, m-3, ... 1. Суммируя все это, вы получите 1 + 2 + .. + m-1 = (m-1) * m / 2 = O (m ^ 2)