计算整数列表的均值、最小值、最大值和总和 - 复杂性如何？

Question

这是一个一直困扰着我的愚蠢问题。

我有一个包含 10 万个数字的列表，我正在为其计算一些统计数据。具体来说，我正在计算这些数字的平均值、最小值、最大值和总和。我正在用折叠来做。在 JavaScript:

// define folding functions:
let mean = (a, b, index, array) => a + b / array.length
let max = (a, b) => Math.max(a, b)
let min = (a, b) => Math.min(a, b)
let sum = (a, b) => a + b

let fold = initial => f => data =>
  Math.round(data.reduce(f, initial))

// functions we can consume:
let averageDistance = fold(0)(mean)
let maxDistance = fold(-Infinity)(max)
let minDistance = fold(Infinity)(min)
let totalDistance = fold(0)(sum)

// compute stats:
let data = [1, 2, 3, ...]
let a = averageDistance(data)
let b = maxDistance(data)
let c = minDistance(data)
let d = totalDistance(data)

对于每个统计 averageDistance、maxDistance 等，这个时间复杂度显然是 O(n)。计算所有 4 个统计，复杂度是 O(4n).

现在，我可以使用 transducer（与 Haskell 的融合类似的优化）或将所有内容内联到 for循环：

let a = 0
let b = -Infinity
let c = Infinity
let d = 0

for (let i = 0; i < data.length; i++) {
  a = mean(a, averageDistance(data[i]), i, data)
  b = max(b, maxDistance(data[i]))
  c = min(c, minDistance(data[i]))
  d = sum(d, totalDistance(data[i]))
}

这个解决方案只做一个循环，所以直观地说它在 O(n) 时间内完成（比 4n 改进之前）。

但它仍然完成与以前相同的工作量：（100k 整数）*（4 统计数据）= 400k 计算。

一种解决方案真的比另一种更快吗？ space 复杂性的差异（不是时间）？如果对这两个都不是，为什么还要麻烦换能器或融合？

Answer 1

这个函数：

Stats_A(array[1...n])
    sum = 0
    for i = 1 to n do
        sum = sum + array[i]

    avg = 0
    for i = 1 to n do
        avg = avg + array[i]
    avg = avg / n

    min = array[1]
    for i = 1 to n do
        if array[i] < min then
            min = array[i]

    max = array[1]
    for i = 1 to n do
        if array[i] > max then
            max = array[i]

    return (sum, avg, min, max)

还有这个函数：

Stats_B(array[1...n])
    sum = 0
    min = max = array[1]
    for i = 1 to n do
        sum = sum + array[i]
        if array[i] < min then
            min = array[i]
        else if array[i] > max then
            max = array[i]

    return (sum, sum / n, min, max)

两者具有相同的线性时间复杂度O(n)。我们可以将成本分配给基本操作，并为这些函数的时间复杂度计算出更多细节表达式，然后我们会发现 Stats_A 比 Stats_B 做了更多的工作，但不是渐近地更多。我们可以让：

内存访问（read/write）需要时间a
+,-,*,/分别取时间b,c,d,e,
比较 (<, >, =) 需要时间 f

现在我们可以计算更详细的运行时表达式：

这个函数：

Stats_A(array[1...n])
    sum = 0                      // a
    for i = 1 to n do            // a + n * (f + b + a)
        sum = sum + array[i]     // n * (2 * b + 3 * a)
                                 // =   (2 + 4 * n) * a
                                 //   + (    3 * n) * b
                                 //   + (    1 * n) * f

    avg = 0                      // a
    for i = 1 to n do            // a + n * (f + b + a)
        avg = avg + array[i]     // n * (2 * b + 3 * a)
    avg = avg / n                // 3 * a + e
                                 // =   (5 + 4 * n) * a
                                 //   + (    3 * n) * b
                                 //   + (    1 * n) * f
                                 //   + (1        ) * e

    min = array[1]               // 2 * a + b
    for i = 1 to n do            // a + n * (f + b + a)
        if array[i] < min then   // n * (2 * a + b + f)
            min = array[i]       // n * (2 * a + b)
                                 // =   (3 + 5 * n) * a
                                 //   + (1 + 3 * n) * b
                                 //   + (    2 * n) * f

    max = array[1]               // 2 * a + b
    for i = 1 to n do            // a + n * (f + b + a)
        if array[i] > max then   // n * (2 * a + b + f)
            max = array[i]       // n * (2 * a + b)
                                 // =   (3 + 5 * n) * a
                                      + (1 + 3 * n) * b
                                      + (    2 * n) * f

    return (sum, avg, min, max)  // =   (5        ) * a

    // total:   (13 + 18 * n) * a
    //        + ( 2 + 12 * n) * b
    //        + ( 1         ) * e
    //        + (      6 * n) * f
    //        = n * (18a + 12b + 6f) + (13a + 2b + e)

还有这个函数：

Stats_B(array[1...n])
    sum = 0                           // a
    min = max = array[1]              // 3a + b
    for i = 1 to n do                 // a + n * (f + b + a)
        sum = sum + array[i]          // n * (3 * a + 2 * b)
        if array[i] < min then        // n * (b + 2 * a + f)
            min = array[i]            // n * (b + 2 * a)
        else if array[i] > max then   // n * (b + 2 * a + f)
            max = array[i]            // n * (b + 2 * a)

    return (sum, sum / n, min, max)   // 5a + e

    // total:   ( 9 + 12 * n) * a
              + ( 1 +  7 * n) * b
              + ( 1         ) * e
              + (      3 * n) * f
              = n * (12a + 7b + 3f) + (9a + b + e)

第一个函数比第二个函数花费的时间严格；在极限情况下，它们的运行时间之比接近它们斜率的商：

(18a + 12b + 6f) / (12a + 7b + 3f)

我们可以观察到分母严格小于分子的2/3；因此，该比率严格大于 3/2。我们预计，对于任何给定的输入，随着输入大小无限制地增加，Stats_A 比 Stats_B 花费的时间接近 50%。

计算整数列表的均值、最小值、最大值和总和 - 复杂性如何？

Calculating mean, min, max, sum of a list of integers - what's the complexity?

javascript

complexity-theory

computer-science

haskell

time-complexity