面试题：Ruby代码复杂度分析之循环优化

Question

给定一段Ruby代码，其中包含多层嵌套循环来处理一个二维数组。请分析该代码的时间复杂度，并提出至少一种优化方案，以降低代码复杂度。代码示例如下： ```ruby array = Array.new(10) { Array.new(10) } result = [] for i in 0...array.length for j in 0...array[i].length for k in 0...array[j].length result << array[i][j][k] end end end ```

Answer 1

时间复杂度分析

这段代码有三层嵌套循环。最外层循环执行 array.length 次（这里 array.length 为10），中间层循环对于外层循环的每一次迭代执行 array[i].length 次（这里也为10），最内层循环对于中间层循环的每一次迭代执行 array[j].length 次（同样为10）。 因此，总的操作次数为 (10\times10\times10 = 10^3) 次。在一般情况下，假设数组维度为 (n)，时间复杂度为 (O(n^3))。

优化方案

1. 减少不必要的循环：从给定代码来看，原代码假设 array 是一个三维数组，但实际创建的是二维数组（Array.new(10) { Array.new(10) }），因此最内层循环是多余的。优化后的代码如下：

array = Array.new(10) { Array.new(10) }
result = []
for i in 0...array.length
  for j in 0...array[i].length
    result << array[i][j]
  end
end

优化后代码只有两层循环，时间复杂度降为 (O(n^2))。

2. 使用 flatten 方法：Ruby 数组有 flatten 方法可以将多维数组展平为一维数组。优化后的代码更简洁，如下：

array = Array.new(10) { Array.new(10) }
result = array.flatten

这种方式同样将时间复杂度降为 (O(n^2))，并且代码更加简洁易读。