复杂的代码段第2部分

的给出了下面的代码片段的复杂性输入尺寸 N个方面：复杂的代码段第2部分

for(int i=0;i<n;i++) // n* 
    for(int j =1;j<=n;j=j*2) // n/2 (its half n, but I assume it still counts as n, or is it log(n)?) 
     a[i]=a[j-1]/2; // 1 

for(int i=0;i-n;i++) // n* 
    if(a[i] %2==0) // 1* 
     a[i]=2*a[i]; // 1

你从下往上开始。复杂性：n^2 + n它是O（n^2）吗？

有什么地方可以了解如何计算简单算法的复杂性？

来源

2011-08-20 Evgeny C

如果您向我们展示您的答案有多远，我们可以为您提供更多帮助。 – rossum

我做到了。下面的代码公式和在注释中：// n代表复杂性，我认为这条线是成立的。谢谢。 –

当你怀疑，

for(int j =1;j<=n;j=j*2)

这是O（LOGN），因为每个迭代j被乘以2，所以总时间为O（nlogn）。至于在哪里看，我喜欢算法简介，但任何优秀的教科书都足以满足简单算法的分析。

来源

2011-08-20 15:04:36

复杂的代码段第2部分

回答

相关问题