В последнее время было лень что-то писать. Очень лень. Но я собрался и решил написать о довольно лёгкой и в тоже время нужной теме - временные оценки для алгоритмов. Их цель - примерно оценить алгоритм по времени работы, в зависимости от входных данных и дать возможность сравнить алгоритмы, не имея их реализации. В прицепе, у всех алгоритмов есть особенности и если они[алгоритмы] легко и быстро реализуемы, то в конкретном случае сравнение на "практике" будет намного информативнее.
Об обозначениях: обычно используется O-натация, то есть обозначается как О(f(x)) или o(f(x)). Первое можно интерпретировать, как c*f(x), c>1, во втором случае 0<c<=1. Сама функция f(x) может быть, как непрерывной. так и дискретной, под x здесь понимается размер входных данных. Например x=n - длина массива, то функция будет дискретной, x=l - длина отрезка, функция будет непрерывной.
И теперь к самой теме: характеры роста, то есть вид функции f(x). Перечислять их буду в порядке возрастания временных затрат: сначала самые быстрые, затем все более медленные.
И теперь, наглядное изображение написанного. Графики указанных функций.Об обозначениях: обычно используется O-натация, то есть обозначается как О(f(x)) или o(f(x)). Первое можно интерпретировать, как c*f(x), c>1, во втором случае 0<c<=1. Сама функция f(x) может быть, как непрерывной. так и дискретной, под x здесь понимается размер входных данных. Например x=n - длина массива, то функция будет дискретной, x=l - длина отрезка, функция будет непрерывной.
И теперь к самой теме: характеры роста, то есть вид функции f(x). Перечислять их буду в порядке возрастания временных затрат: сначала самые быстрые, затем все более медленные.
- Полиномиальный рост
- f(x) = log(x) - логарифмический рост, считается одной из лучших оценок. Поскольку log(x) ~ x^a, 0<a<1 при больших x, то этот рост можно назвать минимальным из полиномиальных. Поскольку оценка определяется с точностью умножения на константу, то основание логарифма не важно.
- f(x) = x^a, a >1 - общий вид полиномиального роста, является приемлемой оценкой. Чем меньше показатель степени a, тем оценка лучше - времени меньше. Как было указанно выше рост вида x*log(x) можно привести к этому типу роста
- Экспоненциальный рост Здесь небольшая путаница в терминологии, при оценки алгоритмов часто любой не полиномиальный рост называют экспоненциальным.
- f(x) = e^x - экспоненциальный рост, рост в геометрической прогрессии. Является не очень хорошей оценкой для работы, однако обычно не критической. Если есть полиномиальный алгоритм, решающий эту задачу - лучше выбирать его.
- f(n) = n!, f(x) = Г(x) - факториальный рост, его спокойно можно включать в следующую группу, однако такие оценки тоже часто встречаются. Поясняю, почему здесь две функции - факториал достаточно известная оценка, но она определенна только для дискретных величин, для непрерывных общение факториала - гамма-функция.
- Алгоритмы, от которых лучше бежать подальше Врятле такие оценки вы когда-нибудь встретите, они здесь больше для сравнения - может быть и хуже.
- f(n) = sf(n) - суперфакториальный рост. sf(n) = 1! * 2! * .. * n! - произведение факториалов. Растёт очень быстро.
- f(n) = (n!)^(n!) - я не думаю, что у такой зависимости есть название вообще. При увеличении n на единицу порядок порядка n увеличивается на единицу. Убунтовский калькулятор (9!)^(9!) на нетбуке уже считает оооочень долго(за 10 минут не посчитал), а виндосовский уже (7!)^(7!) не считает - переполнение.
Вот первые функции.
Добавил (n!)^(n!) на график, только при n=1,2,3,4. Для сравнения: с (4!)^(4!) смогло сравняться только 32!. Ну а что дальше - понятно.
Так что, выбирая алгоритм будьте осторожны - одно и туже задачу, бывает, можно решить очень разными способами.
Комментариев нет:
Отправить комментарий