Подсчет общего количества циклов

Question

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

count = 0;
for i = 1 to n
    for j = 1 to n - i
       count = count + 1

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

Может ли кто-нибудь помочь мне объяснить это мне?

Спасибо

Answer 1

Для каждого iвнутренний цикл выполняется n - i раз (n постоянно). Поэтому (так как i колеблется от 1 в n), чтобы определить общее количество выполнений самого внутреннего оператора, мы должны оценить сумму

(n - 1) + (n - 2) + (n - 3) +... + (n - n)

Переставляя термины (группируя все ns, которые появляются первыми), мы можем видеть, что это равно

n*n - (1 + 2 + 3 + ... + n) = n*n - n(n+1)/2 = n*(n-1)/2 = n*n/2 - n/2

---

Вот простая реализация в Python, чтобы проверить это:

def f(n):
    count = 0;
    for i in range(1, n + 1):
        for _ in range(1, n - i + 1):
            count = count + 1
    return count

for n in range(1,11):
    print n, '\t', f(n), '\t', n*n/2 - n/2

Выход:

1 0 0
2 1 1
3 3 3
4 6 6
5 10 10
6 15 15
7 21 21
8 28 28
9 36 36
10 45 45

Первый столбец n, второе - это количество раз, которое выполняется внутреннее выражение, а третье - n*n/2 - n/2,