BigO
Виды сложностей
O(1) - Константа. Быстро, круто
O(log(n)) - Логарифмическая. Всё равно очень крутая.
O(n) - Линейная. Среднячок.
O(n x log(n)) - Любая сортировка выдает такую сложность. В принципе не сильно хуже чем O(n)
O(n^2) - Квадратичная. Плохо, нужно что-то мутить, туда-сюда. Как-то хитрить.
O(2^n) - Экспоненциальная. Ну это пиздец, это никуда не годиться.
Почему динамический массив при Асимптотическом анализе это O(1) ?
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| size | 1 | 2 | 4 | 4 | 8 | 8 | 8 | 8 | 16 | 16 | 16 | 16 |
| cost | 1 | 2 | 3 | 1 | 5 | 1 | 1 | q | 9 | 10 | 11 | 12 |
Док-во