java - Java中创建大量点的算法

Question

我正在尝试设计一种在正方形中创建随机点的算法。

问题是：如果我们有一个 mxm 正方形，我们会随机创建 n 个 1 < n < m² 的点

算法必须高效，这意味着如果 m = 500，我们可以有 n = 1000 或 n = 100 000。算法的成本必须相同。所以 m 不应该是成本的一​​个因素。

我真的不知道该怎么做......我首先要这样做：

for (int n = 1000, n > 0, n--) {
create a point
}

但是这种方式 m 是成本的一​​个因素......

您知道任何可以提供帮助的算法吗？

谢谢

马特

Answer 1

你的要求在我看来是不可能的。

你说你需要创建n点，从到 的n任何数字。1m^2

应该清楚的是，如果m增长，获得更高的概率会n增加。因此，随着m增长，您将创建的点数 ( n) 必须增长。

创建一个点是恒定的时间，并且独立于创建的任何其他点。因此，随着增长，生成点n所需的工作也会增加。n

但是，使用 Big Oh，以下算法将需要O(m^2)时间来创建n点：

Random r = new Random();
int m; // something
int n = r.nextInt(m*m-1) + 1; // random number between 1 and m^2
for(int i = 0; i < n; i ++) { 
    // create a random point in the square 
    Point p = new Point(r.nextInt(m), r.nextInt(m));
}

Answer 2

我的猜测是该算法将始终是O(n)最坏的情况。这里的假设是您的教授使用 Big-O 的定义是最坏的情况，而不是最佳或平均情况下的表现。因此，我相信这m始终是因素，无论它是什么。