3 ms·
Maybe I’m not clever enough, but wouldn’t the naive implementation of the naive algorithm be O(n^2) operations? Depending on whether you have a linked list or a
by rflrob 6y ago
Maybe I’m not clever enough, but wouldn’t the naive implementation of the naive algorithm be O(n^2) operations? Depending on whether you have a linked list or an array, traversing to or removing a random element takes O(n) time, which you need to repeat n times.
- Znafon 6y agoThe Fisher-Yates algorithm has O(n) running time but it is slightly different than what the author suggested, instead of removing the element from the array, you swap it with the last, that way you are sure not to get it again by simply reducing the upper bound of your random function and it's a O(1) operation so the total running time is O(n): https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#T...