T(sqrtn) + 5 的大 O 符号
Big-O notation of T(sqrtn) + 5
我遇到一个问题：T(N) = T(sqrt(N)) + 5.
请问这样可以解决吗？
T(N) = O(平方(N)) + O(5)
因为O(5) = O(1)是一个常数，我们可以忽略它。
所以T(N)的大O表示法是O(N^(1/2)).
或者我可以说它的符号是 O(N) 因为 O(N) 和 O(sqrt(N)) 之间没有太大区别。
谢谢！
编辑：我在原来的答案中犯了一个错误，假设 n 是 2 的幂并将递归减少到 1, 2, 4, ... n, 这是错误的。我为误导道歉。这是更新后的答案。
来自，
T(n) = T(sqrt(n)) + 5,
我们也可以写成：
T(n) = T(n^(1/2)) + 5,
然后重复:
T(n^(1/2)) = T(n^(1/4)) + 5,
T(n^(1/4)) = T(n^(1/8)) + 5,
...
T(n^(2^-m)) = T(n^(2^-(m+1)) + 5,
这没有显示我们可以停止的常量。因此我们需要替换 n.
尝试：
n = 2^(2^m),
我们在哪里
m = log log n
从m = 0开始，即n = 2,
然后我们有：
T(n) = T(2) + 5 + 5 + ... + 5,
有多少个5？
我们这样算：
2^(2^0), 2^(2^1), 2^(2^2), ... 2^(2^m)
所以有m 5s，其中m = log log n。所以
T(n) = T(2) + 5 log log n,
也就是说，
T(n) = O(log log n).
（为了简洁起见，让我们用常量 c 替换 5）
将这个函数多次代入自身，我们可以发现一个模式出现：
我们什么时候停止迭代？当满足停止条件时。将其设为 n = 2（不是通常情况下的 1，因为参数渐近于 n = 1）：
所以这个函数的最终成本是：
请注意，常数 c (= 5) 与 渐近复杂度 无关。 （而且结果不仅仅是 log n 而是 log log n）
编辑：如果您要选择不同的停止条件 n = a, a > 1，则上述步骤将变为：
与原始结果仅相差常量。
我遇到一个问题：T(N) = T(sqrt(N)) + 5.
请问这样可以解决吗？
T(N) = O(平方(N)) + O(5)
因为O(5) = O(1)是一个常数，我们可以忽略它。
所以T(N)的大O表示法是O(N^(1/2)).
或者我可以说它的符号是 O(N) 因为 O(N) 和 O(sqrt(N)) 之间没有太大区别。
谢谢！
编辑：我在原来的答案中犯了一个错误，假设 n 是 2 的幂并将递归减少到 1, 2, 4, ... n, 这是错误的。我为误导道歉。这是更新后的答案。
来自，
T(n) = T(sqrt(n)) + 5,
我们也可以写成：
T(n) = T(n^(1/2)) + 5,
然后重复:
T(n^(1/2)) = T(n^(1/4)) + 5,
T(n^(1/4)) = T(n^(1/8)) + 5,
...
T(n^(2^-m)) = T(n^(2^-(m+1)) + 5,
这没有显示我们可以停止的常量。因此我们需要替换 n.
尝试：
n = 2^(2^m),
我们在哪里
m = log log n
从m = 0开始，即n = 2,
然后我们有：
T(n) = T(2) + 5 + 5 + ... + 5,
有多少个5？ 我们这样算：
2^(2^0), 2^(2^1), 2^(2^2), ... 2^(2^m)
所以有m 5s，其中m = log log n。所以
T(n) = T(2) + 5 log log n,
也就是说，
T(n) = O(log log n).
（为了简洁起见，让我们用常量 c 替换 5）
将这个函数多次代入自身，我们可以发现一个模式出现：
我们什么时候停止迭代？当满足停止条件时。将其设为 n = 2（不是通常情况下的 1，因为参数渐近于 n = 1）：
所以这个函数的最终成本是：
请注意，常数 c (= 5) 与 渐近复杂度 无关。 （而且结果不仅仅是 log n 而是 log log n）
编辑：如果您要选择不同的停止条件 n = a, a > 1，则上述步骤将变为：
与原始结果仅相差常量。