确定程序的时间和空间复杂度

Question

因此，我在实习中遇到了编码挑战，其中一部分是确定我的程序的空间和时间复杂性。程序大致如下。

while(A){
  int[][] grid;
  // additional variables

 while(B){ //for loop involves iterating through grid
  // additional variables
  for(...) 
    for(....)
 }

  for(...) //for loop involves iterating through grid
    for(....)
}

所以我说的是，程序总体的时间复杂度为 (A N^2+B N^2)，因此得出结论，它的摊余时间为 O(N^2)。

至于空间复杂度，我是否应该将所有变量使用的数字空间相加？假设每个变量都是 int，并且循环 A 中有 3 个变量，循环 B 中有 2 个变量，那么空间复杂度是 (A*24 + B*16)？

Answer 1

为了避免错误，我倾向于使用一种方法，即为每行做一个旁注，表示它被执行的次数（更准确地说，您可以包括最好的情况和最坏的情况）。

考虑到这个例子，这个想法可能如下所示：

num_exec   
        | while(A){
A       |   int[][] grid;
A       |   additional variables
        |
        |   while(B){ //for loop involves iterating through grid
AB      |     additional variables
ABN^2   |     for(...) 
        |       for(....)
        |   }
        |
AN^2    |  for(...) //for loop involves iterating through grid
        |    for(....)
        | }

要估计代码的时间复杂度，可以对这些旁注数字进行简单求和（正如您可能自己所做的那样，尽管您获得的结果与我的结果略有不同）：

至于你的内存复杂度，你的直觉对于 8 位整数来说是正确的。但是，如果我们谈论原始数据类型，您可以简单地将它们视为常量。因此，您应该相当关心复杂的数据类型，即数组，因为它聚合了多个基元。总而言之，您需要考虑指定用于保存数据的元素的数据大小。

因此，应用于示例：

memory   
        | while(A){
ANk     |   int[][] grid;
A3k     |   additional variables
        |
        |   while(B){ //for loop involves iterating through grid
AB2k    |     additional variables
        |     for(...) 
        |       for(....)
        |   }
        |
        |  for(...) //for loop involves iterating through grid
        |    for(....)
        | }

假设grid尺寸为，大小为的原始数据类型外循环中附加变量的总数为3 ，内循环中附加变量的总数为2，总空间复杂度总计为：

注意，假设上面给出的复杂性 和必须都显着小于并且完全独立于它。

您可能有兴趣对此链接中提供的问题进行进一步解释。希望对您有所帮助（即使由于您提供的粗略细节而只是近似值），祝您好运！