Noobo Droid
Немного про сложность алгоритмов
Здесь напишу самый минимум про тему, что зачастую вызывает панику у новичков.
Виды сложности алгоритмов
О (на самом деле омикрон, но в народе прижилось Big-O) - верхняя граница вычислительной сложности.
Ω (омега) - нижняя граница вычислительной сложности.
Θ (тета) - подразумевает, как О, так и Ω. Алгоритм имеет сложность Θ(N), когда он одновременно обладает сложностью О(N) и Ω(N), то есть определяет точную границу сложности.
Кроме этого встречал еще определение пространственной сложности.
Пространственная сложность - концепция, параллельная временной сложности. Зависимость количества занимаемой памяти от размера входных данных. Пример: вызов рекурсивной функции, каждый вызов которой добавляет новый уровень в стек и занимает память.
На собеседованиях, как правило, вопросы про Ω, Θ и пространственную сложность даже не задают. Поэтому дальше подробнее только про Big-O.
Я встречал различные определения Big-O. Приведу примеры:
Идея Big-O - показать сколько шагов должна сделать машина, чтобы закончить выполнение алгоритма, независимо от ее производительности.
Big-O - показывает верхнюю границу зависимости между выходными параметрами функции и количеством операций, которые выполнит процессор. Big-O описывает скорость роста.
Виды сложности алгоритмов Big-O
Как начать учиться считать сложности алгоритмов?
Это сугубо практический навык, поэтому здесь поможет только практика. Информация по этой теме есть в книгах:
- Макдауэлл - "Карьера программиста"
- Бхаргава - "Грокаем алгоритмы"
Кроме того, мне сильно помогло разобраться хоть на какую-то часть этого вопроса видео, которое пересматривал многократно и в голову дошла информация больше всего после просмотра с ручкой и бумагой в руках. Помогает начать оценивать сложность хотя бы тех алгоритмов, какие пишем сами. Поэтому рекомендую: