Как сложность времени этого цикла O (n ^ 2)?

Question

Как сложность времени этого цикла O (n ^ 2)?

for (int i = n; i > 0; i -= c)
    {
        for (int j = i+1; j <=n; j += c)
        {
            // some O(1) expressions
        }
    }

Кто-нибудь может объяснить?

Answer 1

Предположение

n > 0
c > 0

Первый цикл

Первый цикл начинается с i=n и на каждом шаге вычитает c с i.С одной стороны, если c большое, то первый цикл будет повторяться только несколько раз.(Попробуйте с n=50, c=20, вы увидите).С другой стороны, если c мало (скажем, c=1), то оно будет повторяться n раз.

Второй цикл

Второйцикл такой же аргументации.Если c большое, то оно будет повторяться только несколько раз, если c маленькое, много раз и в худшем случае n раз.

Комбинированное / Большое O

Обозначение Big O дает upper bound для time complexity алгоритма.В вашем случае, объединенная верхняя граница первого и второго цикла дает O(n*n)=O(n^2).