Давайте разбавим практические задачи минуткой
Для того, чтобы сравнивать алгоритмы между собой нам нужно выделить какие-то критерии. Они могут быть самыми разными: сложность понимания, кол-во строк кода, необходимость в специфичном аппаратном обеспечении и так далее. Однако, за основу в первую очередь берется вычислительная сложность алгоритма, и во вторую — количество потребляемой дополнительной памяти. Именно по этим критериям вас будут просить оценить решение на алгоритмических секциях интервью.
Что такое асимптотическая сложность и как ее считать?
Точные академические формулировки можно легко нагуглить (вики), поэтому, давайте попробуем объяснить более простыми и приземленными словами.
По большому счету, сложность — это попытка прикинуть скорость выполнения алгоритма. В реальной жизни мы не сможем вычислить и тем более гарантировать затраченное время в милисекундах, так как это зависит от многих переменных (железо, операционная система, язык программирования, тротлинг, фаза луны и т.д.). Поэтому оценивается количество действий, которые нужно совершить. Чем больше действий, тем дольше будет работать алгоритм.
При этом, мы не пытаемся посчитать точное количество, а примерно прикидываем сколько действий нужно совершить. Более того, так как мы оцениваем решение на стремящееся к бесконечности в объеме входных данных, нас будет интересовать только самый «жирный» элемент формулы без константных множителей, так называемый порядок роста. Действия же, которые не зависят от размера входных данных нас вообще не интересуют.
Так, например, в сортировке пузырьком нам нужно сравнить все элементы попарно между собой (цикл в цикле). Это означает, что мы имеем дело со сложностью n^2. Представьте, что нам нужно сперва отсортировать массив, а потом вывести его значения в консоль. Тогда количество действий будет n^2 (сортировка пузырьком ) + n (последовательный вывод элементов в цикле). Так как нас интересует порядок роста, мы смело откидываем все, кроме самого большого члена формулы — n^2.
Если бы кол-во действий алгоритма можно было описать формулой 3*n^3*log(n) + n^2 + 5, то итоговой сложностью была бы n^3*log(n), потому что мы отбросили константный член 5, n^2 (так как он растет медленнее, чем n^3*log(n)) и константный множитель 3)
Количество действий в алгоритме может отличаться в зависимости от входящих данных. Например, функции сортировки не нужно переставлять элементы местами в уже отсортированном массиве. Поэтому, чтобы дать максимальные гарантии, обычно мы говорим о том, как алгоритм будет работать в худшем случае с самыми «неудобными» данными, то есть применяем
О-нотацию.
Стоит заметить, что в реальных задачах, не оптимальный в теории алгоритм может показать себя сильно лучше, чем оптимальный. Происходит это как раз из-за того, что оценивая ассимптотическую сложность мы предполагаем, что размер входных данных будет стремиться к бесконечности и не учитываем константы, так как по сравнению с бесконечностью они не существенны. Если же вам нужно отсортировать массив из 10 элементов - нет смысла использовать супер-сложные сортировки - скорее всего сортировка пузырьком покажет себя сильно лучше 🙂
P.S. Хочу также рассказать о самой частой ошибке, которую я встречал на собеседованиях. Кандидаты часто забывают учитывать в оценке встроенные функции языка, считая только написанный руками код. Самый классический пример — использование встроенной функции сортировки. Если вы вызываете что-то вроде sort.Ints(nums), помните — это не константное действие, а, скорее всего, n*log(n).
#теория