2020-05-25
193
А теперь сопоставим сложность алгоритма с эффективностью его выполнения. Результат такого сопоставления сведем в таблицу. В этой таблице если алгоритм имеет сложность, указанную в левом столбце, то его эффективность – в правом столбце:
И в заключение нашей сегодняшней темы предлагаю рассмотреть числовой пример, который, я уверена, вас удивит, если не поразит.
Пример.
| 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
