1

我一直在尝试计算我的项目的时间复杂度。如果循环是这样的，有人可以指导我如何计算复杂度。

while (k < K){

    for( int i=0; i<M; i++){

        // if condition
        // sets i = dp
    }

    for(int i=dp; i<M; i++){

        for(int j=0; j<=i; j++){

            // single stmt
        }

        // if else condition
        function call(); // assume this has complexity of N
    }
    k++;
}

并请提供一些关于如何识别存储空间复杂度的建议。

4

3 回答 3

1

此代码的复杂性将是 K* (M+(M*((M*M)/2+(M/2)+N))

  K-times for while loop
  M-times for first for loop
  M*((M*M)/2+(M/2)+N) - for nested for loop

您的嵌套 for 循环产生半矩阵示例

  1
  11
  111
  1111

因为全矩阵复杂度是M*M半矩阵，所以M*M)/2 我们需要添加整个对角线(M/2)

于 2013-06-05T14:29:40.130 回答
1

时间复杂度是通过代码将执行的迭代次数来计算的。因此，当我们剖析代码时，有一个顶层循环将迭代 K 次，因此开始的复杂度为 K。然后在该循​​环内有多个循环，每个嵌套循环的复杂度将乘以顶层循环。所以在顶层循环中，我们有两个 for 循环，一个复杂度为 M，另一个内部有一个嵌套循环，使得该循环的复杂度为 M*j。而 N 为被调用函数 所以把整个代码的复杂度加在一起就是K* (M+(M*(j+N)))

  • K -> 首先用于顶层循环
  • M - > 用于第一个嵌套循环
  • M * (j+N) -> 用于第二个嵌套循环，其中包含一个嵌套循环和一个函数调用
于 2013-06-05T14:35:28.127 回答
0

这段代码的复杂度是 K* (M+(M*(M+N)) 并且它是最大的可能性。

但仍然根据您的代码，它还取决于 dp 设置为 i 的内容，这可以降低复杂性。

那么它可以是

此代码的复杂度为K*(M+(M*((M-dp) + N))。

于 2013-06-05T14:46:18.940 回答