代码之家 › 专栏 › 技术社区 › Remi.b

1D世界中到极点的平均距离

time-complexity performance algorithm c++

Remi.b · 技术社区 · 8 年前

我的世界

想象一个有极点的一维离散世界。让我们用一个1D网格来表示这个世界,其中每个插槽都包含一个极点 I 或不包含极点 -

--------I-I---------I----II-------I-------------I--

n 插槽和 m 极点。我们可以用一个长度向量来表示这个世界 m 列出极点的位置

std::vector<unsigned int> polePositions;

或者使用长度为的布尔向量 n

std::vector<bool> isThereAPole;

兴趣统计和示例

每个插槽都有一个平均距离( averageDistance )所有极点。例如,低于时隙索引2(基于零的计数)

---I-I

到两极的平均距离为

平均距离=(1+3)/2=2

然后,我们可以计算每个时隙的平均距离,并将其平均出来,得到平均距离( averageAverageDistance ). 对于上述示例,

平均平均距离=((3+5)/2+(2+4)/2+(1+3)/2+(0+2)/2+ (1 + 1)/2 + (2+0)/2)/6 = 12/6 = 2

问题

如何计算 平均平均距离 高性能?

通常,在每次调用函数时,我会有大约n=1e6个插槽和大约m=1e5个极点。 n 将在每次调用函数时保持不变,但 m (和 polePositions 或 isThereAPole )将因函数调用而异。

错误的实现

下面是一个简单的实现,以上面的小数据为例

#include <iostream>
#include <vector>
#include <math.h>

double getAverageAverageDistance(std::vector<unsigned int> polePositions, int n)
{
    double averageAverageDistance = 0.0;
    for (int slot = 0 ; slot < n ; slot++)
    {
        double averageDistance = 0.0;
        for (auto& polePosition : polePositions)
        {
               averageDistance += fabs(slot - polePosition);
        }
        averageDistance /= polePositions.size();
        averageAverageDistance += averageDistance;
    }
    averageAverageDistance /= n;
    return averageAverageDistance;
}

int main()
{
  std::vector<unsigned int> polePositions;
  polePositions.push_back(3);
  polePositions.push_back(5);
  int n = 6;

  std::cout << "averageAverageDistance = " << getAverageAverageDistance(polePositions, n) << "\n";
}

正确输出

averageAverageDistance = 2

该程序的时间复杂度为O(nm)。有更好的解决方案吗?

2 回复 | 直到 8 年前

R Sahu 8 年前

下面是6个插槽的问题。

假设所有的位置都被填满了。然后,从每个插槽到其他每个插槽可以在6 x 6矩阵中表示为:

| 0 1 2 3 4 5 |
| 1 0 1 2 3 4 |
| 2 1 0 1 2 3 |
| 3 2 1 0 1 2 |
| 4 3 2 1 0 1 |
| 5 4 3 2 1 0 |

总距离可以通过将所有数字相加并除以来计算总数增加了36。

当槽中没有填充电杆时,可以移除整个立柱。比如说,第二个插槽缺失。您可以删除整个第二列以获取总和。当然,现在的总和需要除以30 不是36。

让我们来表示一列中所有数字的总和。叫它 SUM(i) 哪里 i 是列的索引。

缺少第二行时,可以将总和表示为:

SUM(0) + SUM(2) + ... + SUM(5)

幸运的是,有一个很好的求和模式,您可以表示 总和(i) 作为插槽总数的函数,以及 一、 .

让我们看一下 N = 6 .

SUM(0) = 5*6/2

我们称之为基数和, CSUM .

SUM(1) 通过从中删除5来获得 CSUM 然后加1。

SUM(1) = CSUM - (5-1)

SUM(2) 通过从中删除5和4来获得 CSUM 然后再加上2和1。

SUM(2) = CSUM - (5-2) - (4-1)
=> SUM(2) = CSUM - (5-2) - (5-2)
=> SUM(2) = CSUM - 2*(5-2)

SUM(3) 通过从中删除5、4和3来获得 CSUM 然后加上3,2,和1。

SUM(3) = CSUM - (5-3) - (4-2) - (3-1)
=> SUM(3) = CSUM - (5-3) - (5-3) - (5-3)
=> SUM(3) = CSUM - 3*(5-3)

模式是:

SUM(i) = CSUM - i*((N-1) - i)

在一般情况下,

CSUM = (N-1)*N/2

有了这些知识,如果你知道有极点的槽的指数。这是一个 O(M) 操作(如果有) 是 M 极点。

演示程序:

#include <iostream>
#include <vector>

int SUM(int N, int p)
{
   return (N-1)*N/2 - p*((N-1) - p);
}

int main()
{
   int N = 0;
   int M = 0;

   std::cin >> N;
   std::cin >> M;

   std::vector<int> polePositions;
   for ( int i = 0; i < M; ++i )
   {
      int p;
      std::cin >> p;
      polePositions.push_back(p);
   }

   int s = 0;
   for ( int p : polePositions )
   {
      s += SUM(N, p);
   }

   double average = 1.0*s/(N*polePositions.size());

   std::cout << "Average: " << average << std::endl;
}

给定输入

6
2
3 5

输出为

Average: 2

1201ProgramAlarm 8 年前

我认为这可以在O(m)中完成。

这个 polePositions 向量具有每个极点的位置,也就是从第一个槽到每个极点的距离。取该向量之和,得到从第一个槽到所有极点的总距离(我们稍后将计算平均值)。

当您穿过每个插槽时,总距离将减少 m ,直到您到达一个带有杆的槽,位于位置 p1 . 当我们到达那里时,你加入了 (sum - m) + (sum - 2 * m) + ... + (sum - p1 * m) . 我们可以很容易地跳过这个距离,并通过添加(p1*((sum-m)+(sum-p1*m))/2将其累积到总和中。

一旦我们通过第一个极点,向右的每一步都会将项增加1(当我们离p1越远时),而当我们离所有其他极点越近时,会将项减少m-1。因此,您要重复上一步,为每个插槽添加(sum-(m-2))。

继续,直到您为每个极点添加了条件。最终你会到达中间,这个项会增加而不是减少。

对于最后一项,将最后一个极点右侧所有插槽的总和相加。然后将整个总和除以 n .

(这是一种未经调试的算法。)