T(sqrtn)+ 5的大O表示法 [英] Big-O notation of T(sqrtn) + 5

问题描述

我遇到一个问题: 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)= T(sqrt(n))+ 5，

T(n) = T(sqrt(n)) + 5,

我们也可以将其写为:

T(n)= T(n ^(1/2))+ 5

T(n) = T(n^(1/2)) + 5,

然后按重复发生:

T(n ^(1/2))= T(n ^(1/4))+ 5

T(n^(1/2)) = T(n^(1/4)) + 5,

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.

尝试:

n = 2 ^(2 ^ m)，

n = 2^(2^m),

我们在哪里

m =日志log n

m = log log n

从 m = 0 开始，即 n = 2 ，

那么我们有:

T(n)= T(2)+ 5 + 5 + ... + 5

T(n) = T(2) + 5 + 5 + ... + 5,

那里有5个数字? 我们这样计算:

how many 5s are there? We count like this:

2 ^(2 ^ 0)，2 ^(2 ^ 1)，2 ^(2 ^ 2)，... 2 ^(2 ^ m)

2^(2^0), 2^(2^1), 2^(2^2), ... 2^(2^m)

所以有 m 5s，其中 m = log log n .所以

So there are m 5s, where m = log log n. So

T(n)= T(2)+ 5 log log n，

T(n) = T(2) + 5 log log n,

即

T(n)= O(log log n).

T(n) = O(log log n).

这篇关于T(sqrtn)+ 5的大O表示法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！