Алгоритм создания большого количества точек в Java

Question

Я пытаюсь разработать алгоритм, который создает случайные точки в квадрате.

Проблема в том, что если у нас есть квадрат mxm, мы случайным образом создаем n точек с 1

Алгоритм должен быть эффективным, это означает, что если 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));
}

Answer 2

Я предполагаю, что алгоритм всегда будет O(n) в худшем случае. Здесь предполагается, что ваш профессор использует определение Big-O как наихудшего, а не лучшего или среднего показателя. Поэтому я верю, что m всегда является фактором, независимо от того, что это такое.