Анализ сложности функций

Question

Как узнать стоимость этой функции? Я знаю, что это O (√n), но кроме того, что я пробую много значений n и получаю шаблон, я не знаю, как его найти.

void foo(int n) {
    int x = 2;
    int y = 1;
    while(y <= n) {
        y += x;
        ++x;
    }
}

Answer 1

Посмотрите на y значения, после x итераций значение y будет:

step   1 2 3 4     x
y=     1+2+3+4+...+x

(1) Цикл останавливается, когда y>n, что означает, когда 1+2+...+x>n. В этот момент (когда y>n) мы повторяли x раз (да, то же самое x в предыдущих уравнениях!)

(2) Мы также знаем 1+2+...+x = x(x+1)/2 = O(x^2)

(1) + (2): цикл останавливается, когда x^2>n или после √n итераций.

Answer 2

Давайте посмотрим на значение y после i итераций:

y = 2+...+i Циклы заканчиваются, когда y > n, так что вы действительно спрашиваете, на какой итерации i становится ли это условие истинным?

y > n действительно 2+..+i > n. Мы знаем, что 2+..+i = (n(n+1))/2 -1 так y>n становится (i(i+1))/2 > n+1, который решает для i^2 +i > 2n+2. Должно быть достаточно легко увидеть, что i отсюда O(sqrt(n)). Первое значение, при котором выполняется неравенство y > n, пропорционально sqrt(2n+2).

---

Обратите внимание, что 2+..+i = (n(n+1))/2 -1 из-за известной закрытой формулы sum(1,2,3,...,k) = 1+2+3+...+k = (k(k+1))/2

Answer 3

Что является результатом sum(1,2,3,4,...,t)? это равно:

sum(1,2,3,4,...,t)=(t*(t+1))/2

То есть x в цикле увеличивается на O(t^2). Таким образом, число, которое циклы while будут амортизированы до O(sqrt(n)), потому что y увеличивается на x, пока не достигнет n.