big-O中while循环的时间复杂度
Time-complexity of while loop in big-O
我无法根据输入 n 指示简单 while 循环的时间复杂度。
while 循环执行只要i < n 并且i 比上一次迭代的次数增加1。例如，在第 2 次迭代中，i 递增 1，在第 3 次迭代中，递增 2，依此类推...本质上，循环执行 "final value of t" 次。
func(n):
i = 1
t = 1
while (i < n):
i = i + t
t = t + 1
我的问题是，如何用大 O 表示法表示该算法的时间复杂度？
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))。
我无法根据输入 n 指示简单 while 循环的时间复杂度。
while 循环执行只要i < n 并且i 比上一次迭代的次数增加1。例如，在第 2 次迭代中，i 递增 1，在第 3 次迭代中，递增 2，依此类推...本质上，循环执行 "final value of t" 次。
func(n):
i = 1
t = 1
while (i < n):
i = i + t
t = t + 1
我的问题是，如何用大 O 表示法表示该算法的时间复杂度？
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))。