Производный цикл while выполняется в $ \ Theta (\ sqrt {n}) $

Question

Я точно знаю, что алгоритм A работает в $ \ Theta (\ sqrt {n}) $, но как можно получить этот факт?

Алгоритм A

i = 0
s = 0
while s <= n:
    s += i
    i += 1

Вот о чем я думаю. Мы знаем, что A ограничен сверху O (n), так как мы увеличиваем $ s $ более чем на 1 в каждой итерации. Мы также знаем, что он должен быть ограничен снизу $ \ log n $, так как мы увеличиваем $ s $ на что-то меньше $ 2 ^ i $ в каждой итерации. (Поправьте меня, если я ошибаюсь, это только мои мысли ...).

Теперь, что еще мы можем сказать о A ? Как мы получаем, что его временная сложность равна $ \ Theta (\ sqrt {n}) $?

Answer 1

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

for n in range(100000000, 1000000000, 100000000) :   
    i = 0
    s = 0
    while s <= n:
        s += i
        i += 1

и получите следующие результаты:

    n       | iterations|   sqrt(n)
-------------------------------------
100000000   |   14143   |   10000.00
200000000   |   20001   |   14142.14
300000000   |   24496   |   17320.51
400000000   |   28285   |   20000.00
500000000   |   31624   |   22360.68
600000000   |   34642   |   24494.90
700000000   |   37418   |   26457.51
800000000   |   40001   |   28284.27
900000000   |   42427   |   30000.00

---

РЕДАКТИРОВАТЬ

В соответствии с рекомендациями @WillNess Вы можете узнать больше об этом здесь

Answer 2

Каждый раз, когда мы увеличиваем i, мы добавляем s к i. Таким образом, это означает, что после k шагов s выросло до:

     k
    ---
    \
s = /   i
    ---
    i=0

Эта последовательность известна. После k -ого шага идут T _k чисел с T _k a треугольное число [wiki] . Более короткая формула для T _k равна T _k = i × (i + 1) / 2 . T _k , таким образом, масштабируется квадратично с k .

Таким образом, процесс остановится, когда T _k выше n . Таким образом, мы можем определить, что: T _k > n и, таким образом, k × (k + 1) / 2> T _k итаким образом k ² / 2 + k / 2 - n> 0 . Это квадратное уравнение с дискриминантом d = 1/4 + 2 × n и, таким образом, как (положительное) решение k ₀ = - 1/2 + √d. Таким образом, он масштабируется с √2n .

Answer 3

Как видно из кода s = 1 + 2 + 3 + .... + i (1) и s <= n (2). Первое уравнение также может быть записано как s = i * (i + 1) / 2, что означает, что в i приблизительно sqrt(s * 2) и sqrt(n * 2), и, как мы видим из кода, цикл while выполняется i раз, каждый выполняет O(1) расчет. Поэтому общая сложность составляет O(sqrt(n))