Пока что мы действовали довольно безответственно, используя «О-большое». Пришло время поговорить о реальных вещах и измерить время выполнения программ. Я реализовал четыре приведенных выше алгоритма на языке С на компьютере Pentium II 400 МГц, измерил скорость их работы и экстраполировал данные, сведя их в табл. 8.1. Время выполнения алгоритма 26 обычно отличалось не более чем на 10% от алгоритма 2а, поэтому я не стал выделять его в отдельный столбец.
Таблица 8.1. Скорость работы алгоритмов
Алгоритм 1 2 3 4
Время выполнения 1,Зи3 10 п2 47н log2 п 48м
в наносекундах
Время 103 1,3 с 10 мс 0,4 мс 0,05 мс
решения Ю* 22 мин 1 с 6 мс 0,5 мс
задачи 105 15 дней 1,7 мин 78 мс 5 мс
размером ю6 41 год 2,8 ч 0,94 с 48 мс
ю7 41 тыс. лет 1,7 недели 11 с 0,48 с
Максималь 1 С 920 10 000 1,0х106 2,1х107
ный размер 1 мин 3600 77 000 4,9х107 1,3х109
задачи, 1 ч 14 000 6,0х105 2,4х109 7,6хЮ10
решаемой за 1 день 41 000 2,9x10б 5,ОхЮ10 1,8х1012
При увеличении п в 10 раз 1000 100 10+ 10
время возрастает в
При увеличении времени 2,15 3,16 10- 10
в 10 раз п увеличивается в
Эта таблица дает довольно много разнообразных сведений. Самый главный вывод; выбор правильного алгоритма может очень сильно влиять на время решения задачи. Это особенно подчеркивается в средней части таблицы. Последние две строки показывают, как связаны время решения задачи и ее размер.
Есть еще один важный момент. При сравнении кубического, квадратичного и линейного алгоритмов постоянные множители в выражениях для производительности значат не так уж много. Обсуждение алгоритма с временем выполнения 0(ц!) в разделе 2.4 (см. главу 2) показывает, что для быстрорастущих функций постоянные множители значат еще меньше. Чтобы подчеркнуть важность этого момента, я поставил эксперимент, в котором разница в постоянных множителях была максимально возможной. Алгоритм 4 был реализован на компьютере Radio Shack TRS-80 Model III (бытовой компьютер 1980 года выпуска с процессором Z80 на частоте 2.03 МГц). Чтобы еще больше замедлить его работу, я использовал интерпретатор Бейсика, что замедляет программу в 10-100 раз по сравнению с компилированным кодом. Алгоритм 1 был реализован на компьютере Alpha 21164 с частотой 533 МГц. Время выполнения кубического алгоритма росло по формуле 0,58л3 не,
а для линейного алгоритма — 19,5л мс (то есть 19500000л не или 50 элементов в секунду). В табл. 8.2 показаны результаты экспериментов для различных размеров задачи. |
Главная
Каталог файлов
