c# - 我们可以改进这个 o(mn) 的 bin-counting 算法吗？

Question

我在 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 很大，我希望它尽可能快。

Answer 1

对 data 数组进行排序，然后针对每个区间 - 在 data 中找到该范围内的第一个索引和最后一个索引(均使用二分查找)。通过减少 lastIdx-firstIdx(或添加 +1，取决于 lastIdx 是否包含或不是)。

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

Bonus:如果 data 不断变化，您可以使用 order statistics tree ，同样的方法(因为这棵树可以让你很容易地找到每个元素的索引，并且支持修改数据)。

Bonus2:最优性证明

使用基于比较的算法，这再好不过了，因为如果可以的话，我们也可以解决 element distinctness problem更好。

元素区别问题:

Given an array a1,a2,...,an - find out if there are i,j such that i!=j, ai=aj.

这个问题已知有Omega(nlogn) time bound使用基于比较的算法。

减少:

给定元素差异性问题的实例 a1,...,an - 创建数据=a1,...,an 和区间:[ a1,a1], [a2,a2],..., [an,an] - 然后运行算法。
如果有超过 n 个匹配 - 有重复，否则没有。

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