我们可以改进这个0 (mn)的计数算法吗?

本文关键字：算法 mn 我们 | 更新日期: 2023-09-27 18:09:11

我有一个数组在c#中包含数字(例如int, float或double);我有另一个数组的范围(每个定义为下界和上界)。我当前的实现是这样的:

        foreach (var v in data)
        {
            foreach (var row in ranges)
            {
                if (v >= row.lower && v <= row.high)
                {
                    statistics[row]++;
                    break;
                }
            }
        }

所以算法是O(mn)，其中m是范围的个数，n是数字的大小。

这可以改进吗?因为在实际操作中，n是很大的，我想让它越快越好

我们可以改进这个0 (mn)的计数算法吗?

排序data数组，然后对于每个区间-查找data中在此范围内的第一个索引，以及最后一个索引(都使用二进制搜索)。通过减少lastIdx-firstIdx(或增加+1，取决于是否包含lastIdx)，可以很容易地计算出该区间内的元素数。

这是在O(mlogm + nlogm)中完成的，其中m是data的个数，n是间隔的个数。

奖励:如果data不断变化，您可以使用顺序统计树，使用相同的方法(因为该树允许您轻松找到每个元素的索引，并且支持修改数据)。

Bonus2:最优性证明

使用基于比较的算法，这不能做得更好，因为如果我们可以，我们也可以更好地解决元素独特性问题。

元素区别性问题:

给定一个数组a1,a2,...,an -找出是否有i,j这样i!=j, ai=aj .

这个问题已知有Omega(nlogn)的时间限制，使用基于比较的算法。

减少

:

给定元素独特性问题a1,...,an的实例-创建数据= a1,...,an，间隔:[a1,a1], [a2,a2],..., [an,an] -并运行算法。
如果有多个n匹配-有重复项，否则没有。

上述算法的复杂度为O(n+f(n))，其中n为元素个数，f(n)为该算法的复杂度。这必须是Omega(nlogn), f(n)也是，我们可以得出结论，没有更有效的算法。

假设范围是有序的，您总是取第一个适合的范围，对吗?

这意味着你可以很容易地建立一个下界的二叉树。你找到一个比你的数小的最大下界，然后检查它是否符合上界。如果树是适当平衡的，这可以让你非常接近于0 (nlog m)。当然，如果你不需要频繁地改变范围，一个简单的有序数组就可以了——只要使用通常的二分搜索方法。

使用哈希表可以得到非常接近0 (n)，这取决于范围的结构。如果还订购了data，则可以得到更好的结果。

不涉及数据排序的替代解决方案:

var dictionary = new Dictionary<int, int>();
foreach (var v in data) {
    if (dictionary.ContainsKey(v)){
        dictionary[v]++;
    } else {
        dictionary[v] = 1;
    }
}
foreach (var row in ranges) {
    for (var i = row.lower; i <= row.higher; i++) {
        statistics[row] += dictionary[i];
    }
}

获取数据中每个值出现的次数，然后在范围的边界之间求和。

相关文章：

最新信息: