introduction.md

Оценка сложности

Метод - список одноразовых команд, служащих для длостижения цели. Метод, который всегда требует конечной серии операций,называется алгоритм.

Меньше операций == меньше вычислительной мощности . В случае с большинством алгоритмов, число операций быстро растет с увеличением обьема входный данных. Чтобы избежать непредвиденных сложностей, связанных с раздуваением задачи - нужно ввести временную сложность алгоритмов.

Временная сложность

Временная сложность или T(n) - показывает количество операций, которые алгоритм выполняет при обработке входящих данных обьема n.

По факту T(n) - стоимость работы алгоритма. Ты заплатил и тебе вернули сдачу

Нотация O большое, форма записи используется для выражения доминантного члена функции - общепринятый способ выраежния временной сложноси

По факту O(n) - это заплатить без сдачи.

Омега (Ω ()) описывает нижнюю границу сложности.

По факту омега - ты подсчитал все до последней копейки.

Как дела?

Когда T(n) разные для каждого входного n, то мы прибегаем к случаям.

Случай:

1. Лучший - ситуация, когда для любых входящих данных установленного обьема требуется минимальное количество операций. Например,в сортировке это происходит когда данные уже упорядочены

2. Худший - когда для любых входящих данных данного обьема требуется максимальное количество операций. Во многих алгритмах сортировки такое встречается, когда данные передаются в обратном порядке.

3. Средний - среднее кол-во операций, например с алгоритмом сортировки это производное n элементов на вход.

Оценка затрат времени

Сортировка выбором, внешний цикл for обновляет текущую позицию, с которой ведется работа. Внутренний цикл for выбирает элемент, которые затем подставляется за место этой позиции

const selectionSort = (list: number[]): void => {
    for(let current = 0, current < list.length - 1){
        if (list[current] < list[smalles])
            smallest = current;
        // где-то там сверху должен быть smallest 
        for (let i = current + 1, current < list.length){
            if (list[i] < list[smallest]){
                smallest = i;
            }
    }
}

Рассмотрим худший слуай:

1. Внешний цикл совершит n-1 итераций и в каждой из них выполнит по две операции. 2(n-1)

2. Внутренний цикл выполнит n-1, n-2 и т.д. Просуммируем

    n-1
    ∑i = ( (n-1) * n ) / 2 = (n^2 - n) / 2
    i=1

В целом, T(n) в данном случае складывается из 2n-n внешнего цикла и n^2 внутреннего цикла

    T(n) = n^2 + n -2