2

正方形にランダムな点を作成するアルゴリズムを設計しようとしています。

問題は、mxm の正方形がある場合、1 < n < m² の n 個の点をランダムに作成することです。

アルゴリズムは効率的でなければなりません。つまり、m = 500 の場合、n = 1000 または n = 100 000 のいずれかになります。アルゴリズムのコストは同じでなければなりません。したがって、m はコストの要素であってはなりません。

私は本当に何をすべきかわかりません...私はこれを行うことについてイライラします：

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

しかし、このようにmはコストの要因です...

役立つアルゴリズムを知っていますか？

ありがとうございました

マット

4

2 に答える 2

2

あなたの要件は私には不可能に聞こえます。

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));
}
于 2010-11-16T21:22:57.863 に答える
0

ここでの私の推測では、アルゴリズムは常にO(n)最悪のケースになります。ここでの前提は、あなたの教授が Big-O の定義を最悪のケースであり、最高または平均的なケースのパフォーマンスではないということです。mしたがって、それが何であれ、それが常に要因になると私は信じています.

于 2010-11-16T21:24:21.063 に答える