Средняя сложность случая Алго
Что означает средняя сложность алгоритма?
- Среднее по сложности всех возможных сложностей по разным входам, ИЛИ
- Сложность входа, которая является средней из всех возможных входов.
По мне, когда мы говорим, что средняя сложность случая быстрой сортировки N log(N)Я понимаю, что это для входных данных, которые не смещены в сторону того, чтобы быть уже несколько частично отсортированными или крайне не отсортированными. Эта сложность для случайного ввода, который (по моему мнению) означает вход, который является средним из всех возможных входов. Отсюда и термин средняя сложность.
Пожалуйста, поправьте меня, где я не прав. И что на самом деле означает средняя сложность.