Если алгоритм O (lg (n)) с n = 100 занимает 1 с, как можно рассчитать, сколько времени займет n = 1000? - PullRequest
Новая
       6

Если алгоритм O (lg (n)) с n = 100 занимает 1 с, как можно рассчитать, сколько времени займет n = 1000?

1 голос
/ 29 марта 2019

Я сейчас читаю "Прагматичный программист" Эндрю Ханта и Дэвида Томаса.Я сталкивался с этим отрывком:

"Например, предположим, что у вас есть подпрограмма, которая обрабатывает 100 записей за 1 с. Сколько времени займет обработка 1000? Если ваш код O (1), то, это все равно займет 1 с. Если это O (lgn), то вы, вероятно, будете ждать около 3 с. O (n) покажет линейное увеличение до 10 с, в то время как O (nlgn) займет около 33 с.вам не повезло, что у вас есть подпрограмма O (n ^ 2), а затем бездействуйте в течение 100 с, пока она делает свое дело. А если вы используете экспоненциальный алгоритм O (2 ^ n), вы можете приготовить чашку кофе- твоя рутина должна закончиться примерно через 10 ^ (263) лет. "

Может кто-нибудь показать мне математику того, как он придумал времена для O (lgn), O (nlgn), O (n^ 2), а O (2 ^ n) случаев?Я понимаю, O (1) в режиме реального времени, поэтому n = что-нибудь будет то же 1s.Случай линейного O (n) также имеет смысл, потому что n = 1000 записей - это просто 10x n = 100 записей, что означает, что время выполнения будет 1 с * 10 = 10 с.

1 Ответ

2 голосов
/ 29 марта 2019

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

Возьмите пример O(lg N) (где lg - это обозначение для log<sub>10</sub>), и мы будем предполагать постоянный множитель c, чтобы получить времена (это предположение, скорее всего, является причиной, по которой мои цифры будут отличаться от книги).

Итак, (c * lg 100) дает вам 1второе и, поскольку (lg 100 = 2), это означает (c = <sup>1</sup>/<sub>2</sub>).Применяя это к входному размеру 1000, (<sup>1</sup>/<sub>2</sub> * lg 1000) дает вам 1,5 секунды.

Для O(NlgN), (c * 100 * lg 100) дает вам 1 секунду, а с (100 lg 100 = 200) это означает (c = <sup>1</sup>/<sub>200</sub>),Применяя это к входному размеру 1000, (<sup>1</sup>/<sub>200</sub> 1000 lg 1000) дает вам 15 секунд.

Для O(N<sup>2</sup>), (c * 100<sup>2</sup>) дает вам 1 секунду, а с (100<sup>2</sup> = 10,000) это означает (c = <sup>1</sup>/<sub>10,000</sub>),Применяя это к входному размеру 1000, <sup>1</sup>/<sub>10,000</sub> * 1000<sup>2</sup> дает вам 100 секунд.

И, наконец, случай O(2<sup>N</sup>).

Поскольку (c * 2<sup>100</sup>) дает вам 1 секунду,это означает (c = <sup>1</sup>/<sub>2<sup>100</sup></sub>).Применяя это к входному размеру 1000, (<sup>1</sup>/<sub>2<sup>100</sup></sub> * 2<sup>1000</sup>) дает вам (я разберусь с этим, поскольку числа становятся больше): 

  (1/(2^100)) * 2^1000
= 2^1000 / 2^100
= 2^900
= 8.4 * 10^270 seconds
= 2.6 * 10^263 years (using 86,400 secs/day, 365 days/year).

И это , гдеПоистине огромная фигура.Короче говоря: 

Complexity     Duration     From book
----------     --------     ---------
O(1)                1 s           1 s
O(lgN)            1.5 s           3 s
O(N)               10 s          10 s
O(NlgN)            15 s          33 s
O(N^2)            100 s         100 s
O(2^N)         10^263 y      10^263 y

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

...