Ответы пользователя по тегу Алгоритмы
  • Как доказать или опровергнуть: 1) 2^(n+1)=O(2^N); 2) 2^2N != O(2^n)?

    evgenyspace
    @evgenyspace
    Исследователь
    Подставьте 1, 2, ... 10 и проверьте)

    Если более строго, поделите левую часть на правую, возьмите предел при N -> к бесконечности. Если равенство сохраняется (1 = 1), то верно:

    1. Верно, при большом N: (N + 1) / N = 1
    2. Верно, при любом N: 2^2N / 2^N = 2^N != 1
    Ответ написан
  • Сгенерировать M уникальных случайных чисел в диапазоне от 1..N. Быстрый алгоритм есть?

    evgenyspace
    @evgenyspace
    Исследователь
    Создаете упорядоченный список/массив натуральных чисел от 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)
    Ответ написан
    Комментировать
  • Как сравнить произвольные фигуры?

    evgenyspace
    @evgenyspace
    Исследователь
    Вычислить среднее значение радиуса от 0 до 2 PI, среднеквадратичные отклонения от этого среднего. Можно еще и частоту отклонений включить в анализ, т. е. сколько раз нарисованный круг пересечет эталонный, средний (чем меньше, тем лучше).
    Ответ написан
    Комментировать