0

对于下面的代码段，估计大哦符号中的时间复杂度。

for (int i=0; i< n; i++)

for (int j=0; j*j <n;j++)

for (int k=0; k < n/2;k++)
    System.out.println (i+j+k);

我认为它们是嵌套循环，但我不是 100% 确定。据我所知，第一个循环的最坏时间是 O(n)，第二个是 O(sqrt(n))，第三个是 O(log n)。那是对的吗？我是否只需将这些值相乘以获得整个循环的时间复杂度？

4

5 回答 5

2 
for (int i=0; i< n; i++)  ------------------------------------
                                                             |
    for (int j=0; j*j <n;j++) ----------------------         |
                                                   |         | O(n)
        for (int k=0; k < n/2;k++)  -------        |         |
                                          |O(n/2)  |O(n^1/2) |   
            System.out.println (i+j+k); ---        |         |
                                                   |         |
                              ----------------------         |        
                                                             |
                          ------------------------------------

因此运行时

O(n)*O(n^1/2)*O(n/2) = O(n^(5/2))
于 2013-10-02T05:43:14.930 回答
2

为了扩展 Krypton 的评论，循环如下：

  • 循环1：O（n），正如你提到的
  • 循环 2：O(sqrt(n)) == O(n^(1/2))，正如你所提到的。
  • 循环 3：O(n/2)，去掉常数因子，是 O(n)。

相乘，循环 1 和 3 加起来是 O(n^2)，三个加起来是 O(n^(5/2)) 或 O(n^(2.5))。这是在二次和多项式时间之间的一些奇怪的灰色区域。

于 2013-10-02T05:34:52.547 回答
0 
for (int i=0; i< n; i++) {               // O(n)
    for (int j=0; j*j <n;j++) {          // O(n^0.5)
        for (int k=0; k < n/2;k++) {     // O(0.5*n)
            System.out.println (i+j+k);  // O(1)
}}}

添加相同的范围语句，嵌套语句相乘

O((n)*(n^0.5)*(0.5*n)*(1))= O(0.5*(n^2)*(n^0.5))= O(0.5n^2.5)=O(n^2.5)

于 2013-10-02T05:34:30.753 回答
0

我认为 O(n*(n^(1/2))*(n/2))。但我不确定。

于 2013-10-02T05:31:44.113 回答
0

循环 1 的变化率线性取决于 n -> O(n) -- 线性

循环 2 的变化率取决于 n 的平方根 -> O(n^0.5) -- 分数幂

循环 3 的变化率线性取决于 n/2，但可以去除 1/2 常数 -> O(n/2) -- 线性

因此，整体复杂度为 O(n) * O (n^0.5) * O (n) = O (n^2.5)

查看更多信息：http ://www.brpreiss.com/books/opus5/html/page72.html

于 2013-10-04T16:23:12.177 回答