算法 - VoidCC

的时间复杂度计算什么是以下程序的复杂性：算法

void function(int n) 
{ 
int i, j, k , count =0; 
for(i=n/2; i<=n; i++) 
    for(j=1; j=j + n/2<=n; j++) 
     for(k=1; k<=n; k= k * 2) 
     count++; 
}

现在按照我的理解外循环执行N/2次。内循环执行n/2次，第三个内循环执行记录n次。现在，如果我们将算法的时间复杂度表示为函数T（n）。

T（N）= N/2 * N/2 *日志N = N^2/4 *日志N

现在对于n个项log n中也非常大的输入大小与术语n^2相比较小。所以根据我的理解，算法的时间复杂度必须是O（n^2）。但我已经检查了这个程序的答案，它说答案是O（n^2logn）。

任何人都可以帮助我理解为什么我们不能忽视n值较大的术语log n吗？或者我的计算错了？

来源

2014-11-22 Beast

是，数（n）大于多项式较小，但是当它乘以它仍然是一个因素。 O（log（n））比O（n）慢，但O（nlogn）是一件事情，它和你所得到的相似。 O（nlogn）！= O（n）。一张图可以很好地说明这一点。 – keyser 2014-11-22 17:38:15

感谢keyser。举例来说，如果我们有时间复杂度T（n）= n^3 + n^2 + n那么对于非常大的n值，我们忽略n^2和n这个词，那么为什么我们不能在这里做同样的事情？ – Beast 2014-11-22 17:41:16

是的，我们这样做，因为它们是分开的。渐近地，其他的不会有任何显着的影响，但是渐近地说，O（nlogn）比O（n）增长得更快，因为log（n）大于常数。我喜欢benji对他们如何被删除的插图。 – keyser 2014-11-22 17:42:23

您只能忽略常数值。如果n增加，log（n）也增加。

来源

2014-11-22 17:38:04 axiac

感谢axiac。但是举例来说，如果我们有时间复杂度T（n）= n^3 + n^2 + n，那么对于非常大的n值，我们忽略n^2和n这个词，那么为什么我们不能做同样的事情这里？ – Beast 2014-11-22 17:42:46

@Beast您可以忽略n^2和n，因为您将它们添加到n^3不会像您的示例中那样倍增。 – Everettss 2014-11-22 17:59:54

如果我们假设你的algorihtm得到了运行时间功能（不完全正确）：

T(n)=n/2*n/2*log n =n^2/4*log n= an^2*log(n)

你可以做形式渐近分析：

enter image description here

我们可以很容易证明我们可以找到c1和c2来满足：

enter image description here

所以最后你可以说，你的算法已经得到了复杂性：

enter image description here

来源

2014-11-22 18:20:06 Everettss

算法

回答

相关问题