关于最大连续子数组和算法的时间与空间复杂度假设是否正确？

空间复杂度结论：确实是O(n³) #

你关于空间复杂度的判断是正确的，但核心依据应该是所有生成的子数组的总元素量，而非单纯列举数组数量：

• 算法会生成n(n+1)/2个连续子数组（O(n²)数量级），每个子数组都是Ruby中新建的独立数组（list[idx1..idx2]会复制对应区间的元素生成新数组）。
• 所有子数组的总元素数为sum_{k=1 to n} k*(n - k + 1) = n(n+1)(n+2)/6，这是立方量级（O(n³)）。
• 后续map生成的求和数组仅占O(n²)空间，远小于O(n³)，因此算法的空间复杂度由子数组总元素量主导，为O(n³)。

时间复杂度结论：是O(n³)而非O(n⁴) #

你对时间复杂度的判断有误，具体分析如下：

• 两层循环的总迭代次数是O(n²)，但每次迭代中创建子数组list[idx1..idx2]的时间与子数组长度成正比（O(k)，k为当前子数组的元素个数），这部分的总时间等于所有子数组的长度之和，即O(n³)。
• 执行subs.map(&:sum)时，每个子数组的sum操作同样需要遍历其所有元素，总时间也是O(n³)。
• 最后的max操作仅需遍历O(n²)个求和结果，时间可忽略。
• 整个算法的时间开销由上述两个O(n³)的步骤主导，因此时间复杂度为O(n³)，而非O(n⁴)。

附上原算法代码：

def largest_contiguous_subsum(list)
  subs = []

  list.each_index do |idx1|
    (idx1..list.length - 1).each do |idx2|
      subs << list[idx1..idx2]
    end
  end

  subs.map(&:sum).max
end

内容的提问来源于stack exchange，提问作者Daria