1

这个问题是从过去的试卷中修改的，只是想知道我是否做对了

根据给定整数 n 的操作数计算以下代码的时间复杂度 T(n)：

    for ( int i = 1; i < n*n*n; i *= n ) {
      for ( int j = 0; j < n; j += 2 ) {
         for ( int k = 1; k < n; k *= 3 ) {
         // constant number C of elementary operations
         }
       }
     }

到目前为止，我想出了 n^3 * n * log n = O(n^4 log n)

4

2 回答 2

1

我会去的。

第一个循环是O(1)常数，因为它总是运行 3 次迭代 ( 1*n*n*n == n*n*n)。

for ( int i = 1; i < n*n*n; i *= n )

第二个循环是O(0.5n) = O(n)。

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

第三个循环是O(log n)。

for ( int k = 1; k < n; k *= 3 )

因此算法的时间复杂度是O(n log n)。

于 2013-04-02T00:53:18.357 回答
0

我认为你错过了关键点。我在问题中看不到任何地方，它要求您根据 Big-Oh 计算复杂性。相反，它要求给定整数 n 的操作数。

这是我的解决方案，

对于给定的 n，内部循环变量连续采用以下值：k = 1 ,3^0, 3, 3^2, 。. . , 3^(m-1)

因此，内部循环对变量 j 和 i 的每对值执行 C log3n 操作。

中间循环变量 j 取 n=2 个值，

对于给定的 n，外部循环变量 i 采用三个值，1、n 和 n^2。

因此整段代码的时间复杂度等于T(n) = 3C(n/2)log3n = 1.5Cnlog3n。

您可能想检查一下，但这是我对您问题的解释。

于 2013-04-02T04:22:24.050 回答