如何计算给定代码的复杂度 [英] How to calculate the complexity of a given code

问题描述

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) + 2logn Keep 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 - 2logn We 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.

这篇关于如何计算给定代码的复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！