Оценка сложности алгоритмов
Как оценить насколько быстрая написанная нами программа? Как оценить скорость программы?
Измерить временной шкалой? Минуты, секунды и милисекунды? Но в таком случае одна и та же программа на разных компьютерах будет показывать разные результаты.
Мы можем считать количество операций. И тогда наши показатели не будут зависеть от машины, где запускается программа.
Представим сложность алгоритма как некую зависимость от количества входных данных - n. Тогда мы можем записать примерные виды сложности алгоритмов:
534*n3 + 16*n2 + 256
2n4 + 10
Какой из этих алгоритмов быстрее работает?
Для оценки мы берем только наихудщие случаи с точностью до коэффициента. Представим что n стремится к большому числу. В таком случает понятно, что константы не играют болшой роли. И в практике оценки алгоритма принято брать только худшие слагаемые. Худшие имеются ввиду те, что быстрее всех растет. Если входные данные небольшие, то они быстро работают при любых алгоритмах и нет необходимости. Таким образом мы приходим к таким упрощениям:
n3
n4
Видно, что второй алгоритм дольше работает чем первый. Конечно, это все теоретически. В теории мы берем максимально большие числа. А на практике нужно исходить от тех исходных данных которые есть или которые могут быть.