|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 21 Jul 2001 19:40:20
To : Andrew Ezhguroff
Subject : найти ближайшую бОльшую степень двой ки минус 1
--------------------------------------------------------------------------------
Replying to a message of Andrew Ezhguroff to Max Alekseyev:
>> Hапример, если на вход подано уже "готовое" число вида 2^n - 1, то
>> условие проверится один раз и будет выполнен максимум один условный
>> переход. Т.о. время
>> работы предложенного мной алгоритма существенно зависит от входных
>> данных.
AE> В ХУДШЕМ случае (2^62 для целго со знаком - по условию число int64)
AE> твой цикл будет выполнен 62 раза, а условие проверено 63 раза. А в
AE> варианте АМ в ЛЮБОМ случае потребуется только 6 операций
AE> присваивания.
Я не спорю, что алгоритм АМ _в среднем_ работает быстрее. Hо вы отнюдь меня в
этом не убедили ;-)
Hапример, почему вы рассматриваете только ХУДШИЙ случай? Почему не ЛУЧШИЙ?
Логичнее здесь поступить так: берем _всевозможные_ варианты входных данных и
считаем сколько суммарно потребуется времени/операций на их обработку тому и
другому алгоритму. И на основании полученных результатов уже можно делать
вывод...
Regards, ш.ш
Max ~
--- OS/2 Uptime: 0d 14h 32m 52s 304ms
* Origin: В чем родила мать, в том и помирать. (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
