В чем разница между оригинальным алгоритмом Фишера-Йетса и его современной реализацией?

Разница между оригинальным алгоритмом Фишера-Йетса и его современной реализацией заключается в деталях. 19

Оригинальный алгоритм был описан в 1938 году Рональдом Фишером и Фрэнком Йетсом и предназначен для работы с карандашом и бумагой. 13 В нём использовали заранее вычисленные таблицы случайных чисел как источник случайности. 1

Современный алгоритм предназначен для использования в компьютерах и был представлен Ричардом Дурштенфельдом в 1964 году. 19 Он отличается от оригинального алгоритма в нескольких аспектах: 14

• Источник случайности. 1 Вместо вычёркивания выбранного числа и его копирования в другое место, в современном алгоритме выбранные числа меняются местами с последним ещё не выбранным числом. 8
• Временная сложность. 24 Модификация позволила сократить временную сложность алгоритма до O(n), по сравнению с O(n2) для исходного алгоритма. 24
• Использование памяти. 5 Современный алгоритм работает внутри существующего набора данных, в то время как оригинальный метод требует двух коллекций (источник и назначение), в то время как для современного метода нужна только одна копия данных. 5

Таким образом, современная версия алгоритма Фишера-Йетса более эффективна, чем оригинальная, и лучше подходит для работы с большими наборами данных. 25