Сравнение полиномиальной и экспоненциальной сложности времени

Question

Может кто-нибудь, пожалуйста, посмотрите на изображение и скажите мне, как рассчитывается время для экспоненциальных алгоритмов, то есть 2 ^ n и 3 ^ n.

Answer 1

Из верхнего ряда видно, что при n = 10 выполнение работы занимает 10 мкс. Это означает, что каждая операция занимает одну микросекунду.

Строки с 2 ⁿ и 3 ⁿ вычисляются путем перечисления 2 ⁿ мкс и 3 ⁿ мкс в более удобных единицах. Например, 2 ¹⁰ мкс = 1024 мкс составляет около 0,001 с.

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

Надеюсь, это поможет!