问题描述
Function(int n)
if(n<=2)
return 1;
for(i=n ; i>n/8 ; i-=n/2)
for(j=n ; j>2 ; j=j/2)
syso();
return Function(n/2);
为了进行计算,我做了以下操作:
T(n)= T(n / 2) + O(1)+ 2logn
In order to calculate I have done the following :T(n) = T(n/2) + O(1) + 2logn
- T(n / 2):递归调用
- O(1):if语句。
- 2logn:第一个 for将仅运行2次*(
**我已经假设第二个for循环会将j除以2
** I have assumed that the second for loop will divide the j by 2 meaning that I will have j/2^k times iterations = logn.
用相同的逻辑进行下一步:
T(n)= (T(n / 2 ^ 2)+ O(1)+ 2logN) + O(1)+ 2logn
继续进行直到K步:
T(n)= T(n / 2 ^ k)+ O(1)+ 2 * klogn
With the same logic the next step:T(n) = (T(n/2^2) + O(1) + 2logN)+O(1) + 2lognKeep on going until the K step:T(n) = T(n/2^k) + O(1) + 2*klogn
从第一个 if语句开始,函数将在以下情况下停止n< = 2,因此:
n / 2 ^ k =? 2> k = log(n)-1。
From the first "if" statement the function will stop when n <= 2, therefor:
n/2^k =? 2 > k = log(n) - 1.
现在我将k放入函数中,我得到:
T(n)= T(2 )+ O(1)+ 2(logn)^ 2-2logn
我们知道T(2)= O(1),因为它只是在执行 if语句。
Now I place the k in the function and I get:T(n) = T(2) + O(1) + 2(logn)^2 - 2lognWe know that T(2) = O(1) as it's only doing the "if" statment.
T(n)= O(1)+ 2(logn)^ 2-2logn。
假设我已完成所有步骤,那么复杂度是否为O((logn)^ 2)?
T(n) = O(1) + 2(logn)^2 - 2logn.Assuming all the steps I've done are correct, is the complexity is O((logn)^2)?
或者我的计算有误。
推荐答案
以下是对 Danielle
数值实验的补充。
Here is a derivation to compliment Danielle
's numerical experiment.
正如 Danielle
的评论所指出的那样,外部循环仅执行两次,一次执行 i = n
,一次执行 i = n / 2
。内部循环不依赖于 i
,这使事情变得更容易。
As Danielle
's comment points out, the outer loop only executes twice, once with i = n
and once i = n/2
. The inner loops don't depend on i
which makes things easier.
j 将精确地运行 floor(log2(n))
次,因此,假设 syso()
是 O(1)
:
The loop over j
will run precisely floor(log2(n))
times, so, assuming that syso()
is O(1)
:
ie您的递归关系是正确的,但扩展名不正确。
i.e. your recurrence relation is correct, but the expansion was not.
将停止条件 n< = 2
应用于找到 k
的最大值:
Applying the stopping condition n <= 2
to find the maximum value of k
:
数学笔记:
-
四舍五入的数字与其原始值相差小于1:
A number rounded down differs from its original value by less than 1:
floor(x) = x + O(1)
算术级数 1 + 2 + ... + n = n *(n + 1)/ 2
。
应用以上几点:
与数值结果表明的一致。
Which is consistent with what the numerical results indicate.
这篇关于如何计算给定代码的复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!