Big O Notation - 如何描述不同长度的二维数组？

Question

我无法理解 Big O 表示法对于嵌套数据结构（如二维数组或数组对象）的含义。

场景

对所有数组中的所有值求和。

我所知道的

例如，我的理解是以下数据结构将是 O(n^2)，因为两个维度的长度相同 (3x3)。

// O(n^2)

const arr = [
  [1,2,3],
  [1,2,3],
  [1,2,3],
]

这将是 O(n * m)，其中 n 是第一个维度 (2) 的长度，m 是第二个维度 (3) 的长度。

// O(n * m)

const arr = [
  [1,2,3],
  [1,2,3],
]

我不知道的事

但是二维数组长度不同的数据结构呢？

// Maybe O(n * m)?

const arr = [
  [1,2,3],
  [1,2,3,4,5,6],
  [1,2]
]

let sum = 0

for (let nums of arr) {
  for (let num of nums) {
    arrSum += num
  }
}

// sum = 30

或者值为数组的对象？

// Maybe O(n * m)?

const obj = {
  a: [1,2,3],
  b: [1,2,3,4,5,6],
  c: [1,2]
}

let sum = 0

for (let nums of Object.values(obj)) {
  for (let num of nums) {
    sum += num
  }
}

// sum = 30

我对如何用大 O 表示法表示感到困惑。我的想法是你仍然会使用 O(n * m)，其中 n 是第一维（或数字键）的长度，m 代表第二维（或键）中最长的数组值）。

我的想法是否正确？

Answer 1

其实从复杂度来说，两个例子都在O(n * m)。但是，有时您需要更严格的时间复杂度。在你的例子中，如果我们假设数组的长度是 m_1, m_2, ..., m_n，你可以在 Theta(sum_{i = 1}^{n} m_i) 中说出时间复杂度 id。在这种情况下，您可以根据现有情况简化它。例如，有时，长度之和等于一个常数因子n，例如2n。在这种情况下，时间复杂度将为 O(2n).

Answer 2

没必要把它弄得比现在更复杂。 n 和 m 都是简单的变量。他们描述的内容完全取决于您。实际上，正确选择算法运行时复杂性的基础可能非常重要。

因此对于长度不同的数组的情况，您可以简单地选择 n 作为所有“内部”数组的长度之和。对于有对象的情况，问题可以归结为第一个问题。小吹毛求疵：你依赖于 Object.values 的内部行为；我只是假设它在 O(n).

所以一般来说：选择最准确的问题描述-大小，而不是结构。无论您是对 256 x 256 还是 2 x 32768 数组的所有元素求和，在运行时复杂性方面都不会产生任何差异。

Big O Notation - 如何描述不同长度的二维数组？

Big O Notation - How do you describe a 2D array of different lengths?

algorithm

big-o

time-complexity

场景

我所知道的

我不知道的事