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 是从 1 到 m^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));
}