使用子集获取大数据集平均值的时间复杂度

Question

假设您有一大组数字（大小为 n），并被要求计算数据的平均值。你一次只有足够的 space 和 c 个数字的内存。此数据的运行时间复杂度是多少？

Answer 1

是O(n).

一个基本的（虽然不是特别稳定）算法迭代计算如下：

mean = 0
for n = 0,1,2,.. length(arr)-1
    mean = (mean*n + arr[n])/(n+1)

此算法的一个变体可用于解析 c 组数组中的数据，但它在 n.

中仍然是线性的

即拼出序列化：

拼写出来，你可以这样做：

mean = 0
for m = 0, c, 2c, ..., arr_length -1
    sub_arr = request_sub_arr_between(m,min(m+c-1, total_length(arr)-1))
    for i = 0, 1, ..., length(sub_arr)
        n = m + i
        mean = (mean*n + sub_arr[i])/(n+1)

这仍然是 O(n)，因为我们只为每个 n 做有限数量的事情。事实上，这个答案顶部给出的算法是 c=1 的变体。如果 sub_arr 没有保存在本地内存中，但是 sub_arr[n] 在每一步都被读取，那么我们在任何一步都只存储了 3 个数字。

Answer 2

要计算整个数据集的平均值，复杂度为 O(n)。考虑以下算法：

set sum = 0;
for(i = 0; i < n; i++){ // Loop n times
   add value of n to sum;
}
set average = sum / n;

由于我们可以忽略这两个常量时间操作，所以主要操作（将值添加到 sum）发生了 n 次。

在此特定示例中，您一次只有 'c' 个数字的数据。对于每个单独的组，您需要 O(c) 的时间复杂度。但是，这不会改变您的整体复杂性，因为最终您将进行 n 遍。

为提供一个具体示例，请考虑 n = 100 和 c = 40 的情况，并且您的值在数组中传递。您的第一个循环将有 40 次通过，第二个循环有 40 个，第三个循环只有 20 个。无论如何，您已经完成了 100 次循环。

这还假定获取第二组数字是一个常数时间操作。

使用子集获取大数据集平均值的时间复杂度

Time complexity to get average of large data set using subsets

sorting

algorithm

big-o

即拼出序列化：