Значение средней сложности при использовании обозначения Big-O

Question

Отвечая на этот вопрос , в комментариях началась дискуссия о сложности быстрой сортировки.Что я помню из своего университетского времени, так это то, что в худшем случае QuickSort составляет O(n^2), в среднем O(n log(n)) и в лучшем случае O(n log(n)) (но с более жесткой границей).

Что мне нужно, так это правильныйматематическое объяснение значения average complexity, чтобы четко объяснить, что это такое, тому, кто верит, что запись big-O может использоваться только для наихудшего случая.

Что я помню, чтобы определить среднюю сложностьСледует учитывать сложность алгоритма для всех возможных входов, посчитать, сколько вырожденных и нормальных случаев.Если число вырождающихся случаев, деленное на n, стремится к 0, когда n становится большим, то можно говорить о средней сложности общей функции для нормальных случаев.

Правильно ли это определение или определение средней сложности отличается?И если это правильно, может кто-то заявить это более строго, чем я?

Answer 1

Ты прав.

Большой O (большая тэта и т. Д.) Используется для измерения функций . Когда вы пишете f = O (g), не имеет значения, что означают f и g. Это могут быть средние временные сложности, наихудшие временные сложности, пространственные сложности, обозначение распределения простых чисел и т. Д.

Сложность наихудшего случая - это функция, которая принимает размер n и сообщает вам, каково максимальное количество шагов алгоритма при заданном входе размера n.

Сложность в среднем случае - это функция, которая принимает размер n и сообщает ожидаемое количество шагов алгоритма при заданном вводе размера n.

Как вы видите, сложность в наихудшем и среднем случае - это функции, поэтому вы можете использовать большие O, чтобы выразить их рост.

Answer 2

Если вы ищете формальное определение, то:

Средняя сложность - это ожидаемое время работы для случайного ввода.

Answer 3

Я думаю, что ваше определение правильное, но ваши выводы неверны.

Не обязательно верно, что если доля «плохих» случаев стремится к 0, то средняя сложность равна сложности«нормальные» случаи.

Например, предположим, что 1 / (n ^ 2) случаев являются «плохими», а остальные «нормальными», и что «плохие» случаи занимают ровно (n ^ 4) операций,тогда как «нормальные» случаи занимают ровно n операций.

Тогда среднее число требуемых операций равно:

(n^4/n^2) + n(n^2-1)/(n^2)

Эта функция O (n ^ 2), но не O (n).

На практике, однако, вы можете обнаружить, что время является полиномиальным во всех случаях, а доля «плохих» случаев уменьшается в геометрической прогрессии.Именно тогда вы проигнорируете плохие случаи при расчете среднего.

Answer 4

Давайте сослаться Обозначение Big O в Википедии :

Пусть f и g - две функции, определенные на некотором подмножестве действительных чисел.Кто-то пишет f(x)=O(g(x)) as x --> infinity if ...

Так что предпосылка определения состоит в том, что функция f должна принимать число в качестве ввода и выдавать число в качестве вывода.О каком входном номере мы говорим?Предположительно, это несколько элементов в последовательности для сортировки.О каком выходном номере мы можем говорить?Это может быть ряд операций, выполненных для упорядочения последовательности.Но остановись.Что такое функция? Функция в Википедии :

функция - это отношение между набором входов и набором допустимых выходов со свойством, что каждый вход связан с точно одним output.

Производим ли мы точно один выход с нашим предыдущим определением?Нет, мы неДля заданного размера последовательности мы можем получить широкий разброс количества операций.Таким образом, чтобы убедиться, что определение применимо к нашему случаю, нам нужно свести множество возможных результатов (количество операций) к одному значению.Это может быть максимум («в худшем случае»), минимум («в лучшем случае») или среднее значение.

Вывод состоит в том, что говорить о наилучшем / худшем / среднем случае математически правильно , а использование больших обозначений O без таковых в контексте сложности сортировки несколько небрежно.с другой стороны, мы могли бы быть более точными и использовать большие тэта-нотации вместо больших O-нотаций.

Answer 5

Средний анализ случая делает следующее:

Возьмите все входные данные фиксированной длины (скажем, n), суммируйте все времена выполнения всех экземпляров этой длины и построите среднее.

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