algorithm - big-O中while循环的时间复杂度

Question

我无法根据输入 n 指示简单 while 循环的时间复杂度。

只要 i < n 并且 i 比上一次迭代的次数多 1，while 循环就会执行。例如，在第 2 次迭代中，i 递增 1，在第 3 次迭代中递增 2，依此类推...本质上，循环执行“t 的最终值”次。

func(n):
    i = 1
    t = 1

    while (i < n):
        i = i + t
        t = t + 1

我的问题是，如何用大 O 表示法表示该算法的时间复杂度？

Answer 1

Essentially, the loop executes "final value of t" times.

你已经完成了一半。你知道循环执行了 t 次，现在你只需要解决 t。

当 1..t 的总和大于或等于 n 时，您的循环将结束。通过解决 summation , 我们可以表示为

t*(t-1)/2 >= n

通过重新排列方程以根据 n 显示 t，我们得到

t >= 1/2 (1 - sqrt(1 + 8 n))

但是，我们也知道循环在满足不等式的 t 的最低(第一个)值处结束。让我们称该值为 tn。如果tn是第一个满足不等式的值，那么tn-1就是最后一个满足相反不等式的值。

tn - 1 <= 1/2 (1 - sqrt(1 + 8 n))

据此，我们知道 t 由 sqrt(n) 的某个函数和一些常数上下界定。所以 t 是 Θ(sqrt(n))，这意味着 t 也是 O(sqrt(n))。