关于为O（n^2logn）

-1

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

外环执行n/2的时间，中间循环执行n/2个时间和内LLOP执行LOGN时间。关于为O（n^2logn）

上述函数的复杂度是O（n^2logn），但是n/2和n/2将如何变成n^2？

谢谢

来源

2013-03-12 vinay ss

循环是嵌套的，所以它们的所有计数都会相乘。（n/2）*（n/2）是n^2/4，但常量对于大O无关紧要; n^2/4 = O（n^2）并且是这样写的。

来源

2013-03-12 05:33:17 hobbs

谢谢你，这是有道理的。 – 2013-03-12 05:35:24

对于大O符号，省略了常量：“如果f（x）是几个因素的乘积，则省略任何常数（产品中不依赖于x的项）。（n/2）*（n/2）* logn = 1/4（n^2logn），而1（n/2）*（n^2logn）/4被丢弃以给出O（n^2logn）。

参考： http://en.wikipedia.org/wiki/Big_oh_notation

来源

2013-03-12 05:35:33 wilsonmichaelpatrick

你的算法的确切迭代次数，而其增长的复杂性顺序来推断如下所示：

enter image description here

支持性文件：here

来源

2014-04-04 15:14:47

关于为O（n^2logn）

回答

相关问题