Отличный вопрос! Сложность с определением сложности «среднего случая» состоит в том, что вам нужно задать «усредненное по чему? »
Например, если мы предположим, что элементы массива имеют равную вероятность быть в любом из n! возможные перестановки из n элементов, тогда Ω (n log n), связанная с сортировкой сравнения, остается в силе, хотя я, кажется, помню, что доказательство этого довольно сложно.
С другой стороны, если мы предположим, что в данных есть тенденции (скажем, вы измеряете температуры в течение дня, когда вы знаете, что они обычно имеют тенденцию к повышению, а затем к понижению). Многие реальные наборы данных выглядят так, и есть алгоритмы, такие как Timsort, которые могут использовать эти шаблоны для повышения производительности. Поэтому, возможно, «среднее» здесь будет означать «усредненное по всем возможным графикам, образованным последовательностью возрастания и затем падения с добавлением шумовых терминов». Я не встречал никого, кто работал над анализом алгоритмов в этих случаях, но я уверен, что там была проделана определенная работа, и там могут быть даже некоторые хорошие средние показатели, которые менее известны.