Правила при оценке асимптотической сложности

Cуществуют определённые правила при оценке асимптотической сложности:
image
  1. Постоянные множители и слагаемые можно опускать.
  2. Многочлен более высокой степени растет быстрее.
  3. Экспонента растёт быстрее многочлена.
  4. Многочлен растёт быстрее логарифма.
  5. Слагаемые, которые растут медленнее, можно опускать.
Чтобы понять, что одна функция асимптотически меньше другой, удобно разделить одну на другую и посмотреть на график того, что получилось.
Попробуем показать, что n5=O(2n)n^5=O(\sqrt2^{n}). Получим дробь n52n\displaystyle \frac{n^5}{\sqrt2^{n}}.
Совсем не очевидно, что будет происходить с этим отношением по мере роста nn.
Однако если построить график функции f(n)=n52n\displaystyle f(n)= \frac{n^5}{\sqrt2^{n}}, можно посмотреть, как будет вести себя функция при больших значениях аргумента nn.
image
По графику видно, что отношение стремится к нулю. Это значит, что числитель намного меньше знаменателя. То есть n5n^5 по мере увеличения nn растет медленнее, чем 2n \sqrt 2^n. Поэтому n5=O(2n)n^5=O(\sqrt2^{n}).
Вот еще несколько примеров к правилам выше.
Правило 2: многочлен более высокой степени растет быстрее:
image
По этому графику также видно, что отношение стремится к нулю. Значит, что n2=O(n3)n^2 = O(n^3).
Правило 4: многочлен растёт быстрее логарифма
image
Можно сделать вывод, что nlog⁡n=O(n2)n \log n = O(n^2).
Важно отметить, что основание логарифма обычно не учитывают при оценке «O» большого. Вот почему:
image
«O» большое — мощный инструмент в руках программиста.
Следующие функции часто встречаются на практике при анализе сложности алгоритмов.
На картинке они расположены в порядке увеличения скорости роста.
image
Рассмотрим фрагмент кода. Он не решает какую-то практическую задачу. Цель примера — показать, как оценивать общую эффективность алгоритма, части которого имеют разную вычислительную сложность.
Скопировать кодPYTHON
def some_function(array, num):
    max_elem = max(array) # определяем максимальный элемент в массиве
    b = max_elem / 2
    array.sort() # сортируем массив
    result = []
    for i in range(0, len(arr) - 2): # тройной цикл по длине массива
        for j in range(i, len(arr) - 1):
            for k in range(j, len(arr)):
                # do something
                # ...
                _sum = arr[i] + arr[j] + arr[k]
                if _sum > num:
                    result.append(_sum)
                # ...
    for item in result:
        if item > b:
            print(item)
Оценим сложность алгоритма T(n)T(n). В данном случае nn — длина входного массива array.
Если для некоторых операций непонятно, почему сложность именно такая, ничего страшного. Оценке сложности операций и алгоритмов для разных структур данных посвящены отдельные уроки. Пока можно просто поверить, что, например, сложность сортировки — O(nlog⁡n)O(n \log n).
Перейдём к оценке.
  1. Сначала определяется максимальный элемент в массиве. Для этого нужно просмотреть все элементы. Сложность этой операции O(n)O(n). T(n)=nT(n) = n.
  2. Далее массив сортируется. Сложность этой операции будет O(nlog⁡n)O(n \log n). T(n)=n+nlog⁡nT(n) = n + n \log n.
  3. После этого в коде — тройной цикл по длине массива. На каждой итерации цикла происходит подсчёт суммы, сравнение и добавление элемента в массив, если условие выполнено. Но эти операции добавляют к сложности лишь константный множитель. То есть тройной цикл суммарно добавляет к сложности O(n3)O(n^3). T(n)=n+nlog⁡n+n3T(n) = n + n \log n + n^3.
  4. После выхода из тройного цикла мы проходим по массиву result. В нём будет максимум nn элементов. Для каждого элемента производится операция сравнения и, в случае выполнения условия, вывод на экран. Эти операции также добавляют к сложности константный множитель. Таким образом, последний участок кода суммарно добавляет к сложности алгоритма O(n)O(n). T(n)=n+nlog⁡n+n3+nT(n) = n + n \log n + n^3 + n.
Получили, что T(n)=n3+nlog⁡n+2nT(n) = n^3 + n \log n + 2n.
n3n^3 растет быстрее, чем nlog⁡nn \log n и 2n2n.
То есть, сложность алгоритма будет O(n3)O(n^3).
Вы сможете потренироваться и лучше понять правила, выполняя задания.
В программе вы видите фрагмент кода.
Скопировать кодPYTHON
for i in range(len(input_list)):
    for j in range(len(input_list)):
        if i[i] > i[j] + 1:
          # далее следует код тела условной конструкции
Выберите верное утверждение:
Есть алгоритм: пройти по каждому элементу входного массива, возвести его в квадрат, сравнить результат со значением переменной aa. Если результат окажется больше aa, добавить элемент в новый массив. Какая у этого алгоритма сложность?
Какая вычислительная сложность у алгоритма, представленного фрагментом кода?
Скопировать кодPYTHON
for i in range(len(input_string)):
    if input_string[i] == 'a':
        cnt += 1
        ...
Отметьте, верно ли каждое утверждение:
Выведите номера функций в порядке увеличения асимптотической сложности (через пробел):
1. n51. \ n^5\\ 2. n2. \ n\\ 3. n23. \ n^2\\ 4. n4. \ \sqrt n\\ 5. n35. \ \sqrt[3] n\\ 6. n0.46. \ n^{0.4}\\ 7. n2n\displaystyle 7. \ \frac{n^2}{\sqrt n}\\
Ответ:
4 5 2 6 7 3 1
Правильный ответ:
5 6 4 2 7 3 1