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

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

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

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