问题描述
我遇到一个问题: T(N)= T(sqrt(N))+ 5.
I face a question: T(N) = T(sqrt(N)) + 5.
我想知道我能以这种方式解决吗?
I am wondering can I solve it in this way?
T(N)= O(sqrt(N))+ O(5)
T(N) = O(sqrt(N)) + O(5)
因为O(5)= O(1)是一个常数，所以我们可以忽略它.
Since O(5) = O(1) is a constant, we can ignore it.
所以T(N)的大O表示法是 O(N ^(1/2)) .
So the big O notation of T(N) is O(N^(1/2)).
或者我只能说它的表示法是O(N)，因为O(N)和O(sqrt(N))之间没有太大区别.
Or can I just say its notation is O(N) as there is no big difference between O(N) and O(sqrt(N)).
谢谢！
推荐答案
我在原始答案中犯了一个错误，假设 n 是 2 的幂并将重复次数减少为 1、2、4，... n，，这是错误的.造成误导，我深表歉意.这是更新的答案.
I made a mistake in the original answer, assuming that n is a power of 2 and reducing the recurrence to 1, 2, 4, ... n, which is wrong. I apologize for the misleading. Here is the updated answer.
发件人
我们也可以将其写为:
然后按重复发生:
T(n ^(1/4))= T(n ^(1/8))+ 5
T(n^(1/4)) = T(n^(1/8)) + 5,
...
T(n ^(2 ^ -m))= T(n ^(2 ^-(m + 1))+ 5
T(n^(2^-m)) = T(n^(2^-(m+1)) + 5,
这没有显示我们可以停止的常量.因此，我们需要替换 n .
this doesn't show a constant where we can stop. Therefore we need to substitute n.
尝试:
我们在哪里
从 m = 0 开始，即 n = 2 ，
那么我们有:
那里有5个数字?我们这样计算:
how many 5s are there?We count like this:
所以有 m 5s，其中 m = log log n .所以
So there are m 5s, where m = log log n. So
即
这篇关于T(sqrtn)+ 5的大O表示法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！