Как посчитать дробь?

Question

[Aleksey FRZ]

Не могу понять как у автора получилось около ста. Логарифм дает число 6, как там может получиться цифра приблеженная к 100 ?

Comments

[Sn0wSky]

Никак, тут ошибка. Разве что автор не округлил 30 до 100 ;)
Зачем только постить это, если Вы сами все поняли? :)

[Aleksey FRZ]

Sn0wSky: Это из книги Кормана, Алгоритмы построение и анализ.

[Алексей]

А тема статьи какая? Возможно "приближенные и оценочные вычисления"?

[Aleksey FRZ]

Алексей: Данный пример из раздела, где проводится сравнение алгоритма сортировки вставкой и сортировки слиянием.

[Алексей]

Qui-Gon Jinn: Понятно, тогда Сергей верно угадал. Речь о порядке вычислительной сложности.

[Aleksey FRZ]

Answer 1

[Сергей]

Скорее всего речь идет об О-нотации. Т.о. автору что 30 сек, что 100 сек -- без разницы, ему важен лишь его порядок, соотвественно 30 округляется до 100 в большую сторону.

Answer 2

[Евгений Кучеренко]

У автора плохо с математикой. Очевидно, что в задаче важно время исполнения алгоритма. Вычисления с погрешностью в 300% - плохие вычисления.
P.S.: производительность современных персональных компьютеров ~ 10^11 команд / сек

Comments

[Aleksey FRZ]

Автор сравнивает сортировку вставкой и сортировку слиянием. Возможно, на фоне результата сортировки вставкой, погрешность в 300% выглядет безобидной.