Машинные константы и асимптотический анализ алгоритмов?

Question

[UmOx]

Всем доброго времени суток!

Вопрос появился при изучении асимптотического анализа алгоритмов.
В статье, по которой изучаю, есть абзац о том, что если тестить два разных алгоритма на двух разных машинах (один - линейный, другой - логарифмический; одна - медленная, другая - быстрее), то для размеров входных значений, превышающей некую отметку, алгоритм на медленной машине будет исполняться быстрее за счет его логарифмического роста.
И вот там есть строка "So the machine dependent constants can always be ignored after certain values of input size".
Я не понимаю, о каких машинных константах идет речь и почему их можно игнорировать после определенного размера входных данных.
В общем, вопрос в том, что за машинные константы они имеют ввиду.

Спасибо за внимание.

Answer 1

[Rsa97]

machine dependent constants - это количество тактов на один цикл алгоритма и тактовая частота процессора.
Предположим, что линейный алгоритм O(n) работает на быстром компьютере и каждый цикл выполняется за 1 наносекунду, то есть общее время будет 1×n. Логарифмический алгоритм O(log n) работает на медленном компьютере и каждый его цикл занимает 100 наносекунд, общее время 100×log(n) Посмотрим, как будет меняться время алгоритма при изменении n.

n    | O(n) | O(log n)
1    |    1 |   100
10   |   10 |   200
100  |  100 |   300
1000 | 1000 |   400

То есть, в интервале от 100 до 1000 есть значение n, после которого логарифмический алгоритм работает быстрее даже на более медленном компьютере.
В общем случае значение n можно получить из равенства a×n = b×log(n)

Comments

[UmOx]

Спасибо за объяснение.

Answer 2

[res2001]

По моему речь о характеристиках ЦП, влияющих на производительность, например, тактовая частота, размер кэша и проч.
Игнорировать их можно потому, что алгоритм с логарифмической сложностью будет выполняться быстрее на более медленном устройстве - как раз описанный случай. Для каждых двух разных аппаратных конфигураций и алгоритмов размер входных данных, при котором алгоритм с логарифмической сложностью будет выигрывать у линейного, будет разным и его нужно подбирать опытным путем.
Просто примите к сведению и продолжайте изучение, это не то на чем требуется заострять внимание.

В практических задачах часто оптимизируют алгоритмы для того что бы можно было выполнять задачу на более слабом устройстве, при этом имеют конечную цель снизить энергопотребление устройства. Актуально для разного рода встроенных решений.

Comments

[UmOx]

Спасибо за ответ.