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 |
Док-во
Cколько действий нужно сделать? Каждый раз точно нужно вставлять по единичке,
Сколько раз мы копируем? Мы log(n) по основанию два делаем копирований А всего у нас n операций
Тут типо формула суммы геометрической прогрессии вместо чиселки сколько раз мы копируем.
То есть, (n + log(n)) / n Что равняется = (n+ 2^log(n)-1) / n = ( n +n ) / n = 2
И при Ассимптотическом анализе это будет n / n = 1