1

给定一堆数字，我试图确定在数字非常密集的地方是否存在“团块”。

为了使事情更准确，我想我会问一个更具体的问题：给定一组数字，我想确定是否存在n具有标准偏差 <=的大小子集s。如果有很多这样的子集，我想找到具有最低标准偏差的子集。

所以问题#1：这个正式的问题定义是否有效地捕捉到了密集数字“团块”的直观概念？

  • 编辑：我实际上并不关心确定哪些数字属于这个“团块”，我更感兴趣的是确定团块的中心位置，这就是为什么我认为n提前指定是可以的。但请随时纠正我！

问题 #2：假设确实如此，实现这样的事情的最佳方法是什么（特别是，我想要一个时间复杂度最低的解决方案）？到目前为止，我认为我有一个可以运行的解决方案n log n：

  • 首先，请注意，给定大小的最低标准偏差拥有子集必须由连续数字组成。所以第1步是对数字进行排序（这是n log n）

  • 其次，取第一个n数字并计算它们的标准差。如果我们的数字数组是从 0 开始的，那么第一个n数字是[0, n-1]. 要获得标准偏差，请计算s1和s2如下：

    • s1 = sum of numbers
    • s2 = sum of squares of numbers

    然后，维基百科说标准差是sqrt(n*s2 - s1^2)/n. 将此值记录为迄今为止看到的最高标准偏差。

  • [1, n]找到, [2, n+1], ...的标准差，[3, n+2]直到找到最后一个n数字。如果您跟踪s1和s2运行总计，则每次计算只需要恒定的时间：例如，要获得 的标准差，只需从和总计[1, n]中减去第 0 个元素并添加第 n 个元素，然后重新计算标准偏差。这意味着算法的整个标准偏差计算部分需要线性时间。s1s2

所以总时间复杂度n log n。

我的评价对吗？有一个更好的方法吗？我真的需要它在相当大的场景上快速运行，所以越快越好！空间不是问题（我认为）。

4

1 回答 1

1

最近一直在研究类似的问题，团块的定义和建议的实现似乎都是合理的。

另一个合理的定义是找到所有n数字范围的最小值。因此，如果对数字列表进行了x排序，则只需找到 、 等的最小值x[n]-x[1]。x[n+1]-x[2]这将比找到标准差稍微快一些，因为它可以避免乘法和平方根。实际上，即使在寻找最低标准偏差时，您也可以通过找到最小方差（标准偏差的平方）而不是 sd 本身来避免平方根。

需要注意的是，最大团块的位置可能对 的选择非常敏感n。如果有一个先验的理由来选择一个特定的n，那将不是问题。但是，如果不是，则可能需要进行一些实验来选择n相当可靠地找到您正在寻找的团块的值，无论您是按范围选择还是按标准差选择。这方面的一些想法可以在EDA 的在线书籍 ABC 的第 6 章中找到。

于 2013-06-24T01:51:49.060 回答