А теперь сопоставим сложность алгоритма с эффективностью его выполнения. Результат такого сопоставления сведем в таблицу. В этой таблице если алгоритм имеет сложность, указанную в левом столбце, то его эффективность – в правом столбце:
И в заключение нашей сегодняшней темы предлагаю рассмотреть числовой пример, который, я уверена, вас удивит, если не поразит.
Пример.
n (размер задачи) | O(n) | O(2n) |
50 | 1 сек | 1 сек |
51 | 1,02 сек | 2 сек |
60 | 1,2 сек | 17 мин |
70 | 1,4 сек | 12 суток |
80 | 1,6 сек | 34 года |
90 | 1,8 сек | ~35 тыс. лет |
Список литературы
1. Введение в анализ сложности алгоритмов (часть 1). [Электронный ресурс]. Режим доступа: https://habr.com/ru/post/196560/
2. Введение в анализ сложности алгоритмов (часть 2). [Электронный ресурс]. Режим доступа: https://habr.com/ru/post/195482/
3. «O» большое и «o» малое. [Электронный ресурс]. Режим доступа: https://ru.wikipedia.org/wiki/«O» большое и «o» малое
4. Как сравнивают быстродействие алгоритмов. [Электронный ресурс]. Режим доступа: http://langtoday.com/?p=343