Создаете упорядоченный список/массив натуральных чисел от 1 до N;
Генерируете случайное число от 0 до длины массива - 1;
Забираете из исходного массива элемент с индексом сгенерированного числа и вставляете его в новый массив.
Предполагается, что исходный массив будет обрезан.
Повторяем операцию.
Вроде как раз O(N^2) получается.
Интересно, откуда такая задача?
Я Erlang не знаю, но на JavaScript самое изящное решение выглядит так:
const createArray = (length) => Array.from( {length: length}, (v, k) => k );
const shuffle = (array) => array.sort( (a, b) => Math.random() - 0.5 );
shuffle(createArray(10000));
Теоретическое время работы такого алгоритма -O ( N^2 * Log (N) ), однако как показывают тесты, на практике - O (N)
const test = (n) => {
let start = new Date().getTime();
shuffle(createArray(n));
let finish = new Date().getTime();
return console.log(`Lead time: ${Math.round(finish - start)} msec`)
}
test(10000)
test(100000)
test(1000000)
Средний
