|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 22 Jul 2001 02:17:25
To : Max Alekseyev
Subject : Re: найти ближайшую бОльшую степень двой ки минус 1
--------------------------------------------------------------------------------
Привет! "Max Alekseyev" <Max.Alekseyev@f60.n5015.z2.fidonet.org> сообщил(а)
нам:
> Я не спорю, что алгоритм АМ _в среднем_ работает быстрее. Hо вы отнюдь
меня в
> этом не убедили ;-)
> Hапример, почему вы рассматриваете только ХУДШИЙ случай? Почему не ЛУЧШИЙ?
Ладно, буду рассматривать средний вариант. Хотя ИМХО ориентироваться надо
все же на худший случай (хотя бы, чтобы понимать, что может произойти).
> Логичнее здесь поступить так: берем _всевозможные_ варианты входных данных
и
> считаем сколько суммарно потребуется времени/операций на их обработку тому
и
> другому алгоритму. И на основании полученных результатов уже можно делать
> вывод...
А вот и цифры.
Для всех чисел от 0 до 0x7FFFFFFF твой вариант требует 9106550115
присваиваний и 11254033763 сравнений. Т.е. по 4.24 присваивания и 5.24
сравнения. Что в сумме все же больше, чем 6 присваиваний. И к тому же при
увеличении разрядности числа
среднее кол-во циклов возрастет.
Компилятор gcc 2.95.2, оптимизация O2, диапазон тот же: пустая функция - 79
s, твой алгоритм - 323 s, алгоритм АМ - 191 s. Получаем (учитываем только
чистое время выполнения тела подпрограммы без затрат на вызов, возврат и
пр.), что твой алгоритм в (323-79)/(191-79)=2.8 медленнее. И даже если
учитывать общее время, то разница в 1.69 раз.
С уважением, Андрей.
--- ifmail v.2.15dev5
* Origin: COMSTAR Telecommunications (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
