Этот вопрос относится к алгоритму Фишера-Йейтса для возврата случайного перемешивания данного массива. На странице Википедии написано, что ее сложность составляет O (n), но я думаю, что это O (n log n).
На каждой итерации i случайное целое число выбирается между 1 и i. Простое запись целого числа в память - это O (log i), и, поскольку существует n итераций, общее
O (log 1) + O (log 2) + ... + O (log n) = O (n log n)
что не лучше наивного алгоритма. Я что-то здесь упускаю?
Примечание. Наивным алгоритмом является присвоение каждому элементу случайного числа в интервале (0,1), а затем сортировка массива по назначенным числам.
ds.algorithms
permutations
Томер Вромен
источник
источник
Стандартная модель вычислений предполагает, что арифметические операции над O (log n) -битными целыми числами могут выполняться за постоянное время, поскольку эти операции обычно передаются аппаратно. Таким образом, в алгоритме Фишера-Йейтса «запись целого числа i в память» занимает всего O (1) времени.
Конечно, анализировать алгоритм с точки зрения битовых операций совершенно целесообразно, но модель битовой стоимости менее предсказуема для реального поведения. Даже простой цикл
for i = 1 to n: print(i)требует O (n log n) битовых операций.источник
Это ответ на «Алгоритм Фишера-Йейтса не лучше наивного алгоритма. Я что-то здесь упускаю?» который вы задали в вопросе.
В вашем «наивном» алгоритме, который использует действительные числа: сколько бит точности вы используете? Если вы рассчитываете сложность битов (как вы, кажется, делаете для Фишера-Йейтса), и алгоритм использует k случайных битов для действительных чисел, тогда его время выполнения будет Ω (kn log n), поскольку сравнение двух k- Битовые действительные числа занимают время (к). Но k должно быть не менее Ω (log n), чтобы два элемента не отображались на одно и то же действительное число, а это означает, что алгоритм занимает Ω (n log 2 n) времени, что медленнее, чем случайное перемешивание Фишера-Йейтса на коэффициент логарифма
Если вы просто подсчитываете количество арифметических операций и операций сравнения и игнорируете их битовую сложность, то значение Фишера-Йейтса равно Θ (n), а ваш алгоритм равен Θ (n log n), но все равно с коэффициентом log n отдельно.
источник
В этой задаче нет ничего особенного в целых числах.
Например, хеш-таблицы (хранящие любые значения) не имеют времени O (1) для доступа, если хеш-функция должна прочитать все значение, чтобы вычислить свой хеш. Для n уникальных элементов требуется, чтобы в среднем было представлено n битов для представления, независимо от того, насколько умным является ваше представление, и любая хэш-функция, которая считывает весь ввод, следовательно, будет занимать как минимум столько же времени для вычисления. На практике они быстрее, чем красно-черные деревья, но асимптотически они не лучше.
Шумиха, на которую ссылается randomwalker, была о документе POPL 2008 ( http://portal.acm.org/citation.cfm?doid=1328438.1328460 ), обсуждаемом здесь: http://blog.computationalcomplexity.org/2009/05/shaving- журналы-с-блок-cost.html
В этом посте Ланс Фортноу описывает, как будучи студентом, он жаловался, что для сортировки действительно требуется n log ^ 2 n времени, если мы должны прочитать все log n битов двух элементов, чтобы сравнить их, что кажется разумным возражением.
источник
Фактически, O (n log n) является нижней границей для этой проблемы в моделях, где сортировка O (n log n). Если все перестановки одинаково вероятны, то алгоритм как функция от случайных потоков до перестановок должен быть сюръективным. Нет! перестановки, поэтому в чем-то вроде модели дерева решений есть ветви длиной не менее O (log n!) = O (n log n).
источник
В TCS мы рассматриваем - если не указано иное явно - сложность на машине Тьюринга. Хотя это хорошо для теоретических целей, результаты не очень полезны на практике, поскольку мы реализуем различные модели машин (то есть конечные приближения) в аппаратном обеспечении. Поэтому целесообразно задать сложность этих моделей. Например, мы обычно предполагаем, что машины регистров (подобно реальным процессорам) могут выполнять элементарные операции над двумя регистрами в постоянное время - это то, что могло бы использоваться здесь.
Вкратце: вы думаете с точки зрения ТМ, авторы статьи - с точки зрения РМ. Вы оба правы.
источник