Пока что мы действовали довольно безответственно, используя «О-большое». Пришло время поговорить о реальных вещах и измерить время выполнения программ. Я реализовал четыре приведенных выше алгоритма на языке С на компьютере 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 показаны результаты экспериментов для различных размеров задачи.
Опубликовал vovan666
April 17 2013 00:00:39 ·
0 Комментариев ·
3821 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
