Алгоритмы

BigO Прказывает кк будет меняться производительность алгоритма от роста исходных данных

Time, memory (Время, память)

• Worst case (выбирается худший случай)
• Average case
• Best case

Правильно говорить алгоритм работает со сложностью:

O(n) - линейная зависимость (с ростом входящих данных растет время) (обычный перебор)

O(1) - время константа, с ростом данных остается неизменным (намного лучше линейной сложности) (если есть возможность перенести данные транспортом как пример)

O(log n) - логарифмическая сложность (быстрая сортировка)

O(n log n)

O(n²) квадратичная сложность (два вложенных цикла)

O(n³) кубическая (3 вложенных цикла)

O(2ⁿ) экспоненциальная сложность (расчет n-ого числа Фибоначи)

O(n!) (задача о комивояжере должен посетить все пункты хотябы по разу и вернуться в исходный)

Константы при умножении и делении отбрасываются, при сложении выбирается самый неэффективный алгоритм

Поиск

• Линейный поиск O(n)
• Бинарный поиск O(log₂n)

Сортировка

• Алгоритм выбора O(n²) (неэффективный) (пробегаем по массиву, находим минимальное значение и меняем местами с первым, затем начиная со второго элемента ищем следующее минимальное но меняем его уже со вторым элементом и т.д.)
• Пузырьком O(n²) (неэффективный) сравниваем попарно стоящие элементы, если следующий элемент меньше чем предыдущий меняем местами, получается своего рода всплытие )
• Быстрая сортировка O(log₂n * n)