Почему мы не оцениваем алгоритмы по их сложности в среднем случае

Question

У нас есть три способа оценки алгоритма:
Наихудший случай
Наилучший случай
И средний случай

Первый из них говорит нам, что нужно посмотреть на наихудший возможный вход для алгоритма, иоцените его производительность.

Вторая подсказывает нам взглянуть на наилучшие входные данные для нашего алгоритма.

Последняя подсказывает нам взглянуть на среднюю регистр входных данных для алгоритма, и поэтому это может бытьболее точный показатель производительности алгоритма.

Почему мы не рассматриваем алгоритм по срединному случаю, он должен быть более точным, чем средний случай, или, по крайней мере, дополнительным фактором к нему.Потому что мы смотрим на вход, что половина возможного ввода находится ниже и выше него.

Медиана дает вес, необходимый для ввода, который может не дать avg.

Answer 1

Медиана на самом деле не имеет очень полезных статистических свойств.

Одна вещь, полезная в среднем, заключается в том, что асимптотически маловероятно, что вы получите неверный ввод.

Предположим, что среднее значениевремя вашего алгоритма составляет f(n) в 60% случаев и g(n) в 40% случаев, где g(n) >> f(n).Тогда ваша медиана равна Θ(f(n)), но ваше решение часто не укладывается в интервал времени для алгоритма f(n).Однако даже если вероятность для g(n) является очень маленькой константой, среднее значение все равно будет Θ(g(n)), предупреждая вас о том, что алгоритм может работать в течение длительного времени.

Другим полезным свойством ожидаемого значения является суммирование.Если у вас есть несколько задач, выполняемых последовательно, то среднее общее время выполнения будет равно общему среднему времени выполнения.Это облегчает получение и использование среднего.Для медиан подобного свойства не существует.