Эффективность алгоритма в наилучшем, наихудшем и среднем случаях - EcsFlash/DataTypes GitHub Wiki

Также разделяют эффективность в худшем, лучшем и среднем случаях. Эти эффективности рассматриваются в том случае когда есть зависимость не только от размера входных данных но и от других параметров. Например поиск какого либо элемента обычным проходом в неупорядоченном массиве может выполниться как за константное время(если искомый элемент окажется первым) - лучший случай O(1), так и за линейное время(искомый элемент стоит последним) - одновременно средний и худший случай O(n).

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

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

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

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

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

Средний случай Как бы там ни было, из данного описания уже должно быть понятно, что на основании информации, полученной в результате анализа алгоритма для наилучшего и наихудшего случаев, нельзя сделать вывод о том, как поведет себя алгоритм при обработке типовых или случайно заданных входных данных. Чтобы получить подобную информацию, нужно выполнить анализ алгоритма для среднего случая (average-case efficiency). Для этого нужно сделать ряд предположений о совокупности входных данных размером n.

При анализе в среднем случае мы берём все возможные входные данные и вычисляем время вычисления для всех входных данных. Суммируем все вычисленные значения и делим сумму на общее количество входных данных.

Пример Для примера возьмем линейный алгоритм поиска элемента в массиве циклом for.

func find(arr []int, elem int) bool{
    for i:=0; i < n; i++ {
        if arr[i] == elem {
            return true;
        }
    }
    return false;
}

Лучший случай: постоянное время независимо от размера входных данных. Это произойдет, если искомый элемент находится в первом индексе заданного списка. Таким образом, количество сравнений в этом случае равно 1.

В среднем случае: линейное время, если искомый элемент находится в середине (при среднем поиске) заданного списка.

В худшем случае: искомый элемент отсутствует в списке(либо стоит на последнем месте, и тогда придётся пройти все n элементов массива)