Задача Иосифа Флавия или считалка Джозефуса


Несмотря на теоретический разбор алгоритмов, действительная скорость работы программ иногда сильно отличается от планировавшейся. Одна из причин этого – разная эффективность компилятора при работе с различными структурами данных и циклами, как в данном случае.

Для того чтобы продемонстрировать преимущества и недостатки разных алгоритмов, были написаны демонстрационные программы, определяющие время работы всех алгоритмов для одних и тех же значений.

Тестирование программ проводилось на 2-х компьютерах: с процессором AMD Athlon II X2 245 с операционной системой Windows XP и на ноутбуке Macbook Pro с процессором Intel I7 с операционной системой Ubuntu.

Результаты тестирования на ноутбуке Macbook Pro приведены в таблице:

Способ N=2000
S=2000
N=10000
S=10000
N=50000
S=50000
N=100000
S=100000
N=100000
S=10000
N=100000
S=1000
N=100000
S=100
1 790 мс 23 с 5 мин >10 мин - - -
2 65 мс 1350 мс 33 с 2 мин 14 с - - -
3 16 мс 169 мс 3,9 с 15,6 с 15,8 с 13,8 с 10,1 с
4 13 мс 158 мс 3,7 с 14,8 с 7 с 0,8 с 0,1 с
4 13 мс 153 мс 3,6 с 14,4 с 7 с 0,8 с 0,1 с