Модуль: Расчет асимптотической сложности


Задача

1/9

Расчет асимптотики - 1

Теория

Часто необходимо понимать насколько эффективен написанный код. Для этого обычно оценивают время выполнения и/или затрачиваемую память.
Для выражения этой оценки часто используют асимптотическую сложность (в дальнейшем будем считать, что времени, т.к. по сравнению с памятью значимых отличий нет)
Сложность зависит от переменных входных параметров и выражают ее как функцию, зависящую от размеров этих данных (подробнее в примере в конце теории).
Для оценки сложности нам интересно именно асимптотическое поведение этих функций (отсюда и короткое выражение - "асимптотика кода"), то есть когда входные данные довольно большого размера.
Поэтому используют так называемую О-нотацию. За этим стоит не самая простая математическая теория, в которую углубляться не будем. Желающие могут подробнее ознакомиться на википедии или других интернет-ресурсах.
Однако стоит запомнить, что асимптотику кода почти всегда указывают в этой самой нотации, поэтому стоит самим всегда так делать. На небольшом примере разберемся как примерно это делать.

Как очевидно из названия, функции записываются внутри скобок, обозначенных большой буквой "O". Например: О(n), O(nm), O(log(c)), где как n, m, c или др. мы обозначаем потенциальные размеры входных данных.
Теперь о том, как саму асимптотику считать.
1) Для начала надо понять от размера каких данных зависит время выполнения программы. Сопоставим размеру этих данных переменные, в контексте которых и будем вычислять асимптотику. Обычно их обозначают буквами n, а затем m.
2) Далее выразим реальное время работы через эти переменные. Если некоторые части сложно посчитать точно, то оценивают приблизительно и сверху (то есть преувеличивают с запасом), т.к. предположить, что программа тратит больше ресурсов, чем на самом деле, не страшно, а вот обратная ситуация потенциально может приводить к проблемам.
3) После этого среди всех слагаемых возьмем самое "тяжелое". Их может быть несколько, если их нельзя сравнить (например разные переменные, т.е. размеры разных входов, т.к. мы не знаем заранее что именно программа получит на вход). Далее опускаются константные множители у этих слагаемых (даже если изначально было, например, 100000n или 0.00001n, то остается только n) и после этого результат записывается в О-нотации.

Разберем небольшой пример.
Предположим, что у нас есть программа, которая принимает на вход массив целых чисел и сравнивает количество обменов, необходимых для сортировки пузырьком этого массива и сортировки слиянием. 
Здесь время работы программы зависит только от входящего массива. Обозначим за n его размер.
Посчитаем реальное время работы. n итераций на считывание массива, сортировка пузырьком, которая в худшем случае будет использовать n*(n-1)/2 обменов (здесь нам важно учитывать именно худший случай), сортировка слиянием, время которой тяжело оценить точно, но оценим его сверху как 10*n*log(n) (т.к. мы знаем, что она работает за О(n*log(n)), но как уже было сказано, константы опускаются)
Итого примерное время работы: n + n*(n-1)/2 + 10*n*log(n) = n + n^2/2 - n/2 + 10*n*log(n). Довольно понятно, что 1ое и 3ее слагаемые здесь не являются определяющими. Вопрос лишь в том, что "тяжелее", 2ое или 4ое.
Заметим, что при небольшом n, например, при n=4, 4ое слагаемое имеет на порядок большее значение, чем 2ое (8 против 80). Однако это не имеет никакого значения, как раз потому, что мы проводим асимптотический анализ, то есть предполагая, что входные данные довольно большого размера, например, n=1000000. При таком размере входных данных уже наглядно видно, насколько n^2/2 на самом деле превышает 10*n*log(n).
В итоге мы оставили самое "тяжелое" слагаемое n^2/2 и теперь проигнорируем его константный множитель 1/2. Таким образом, асимптотика данного алгоритма равна О(n^2).

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

Задача

Для приведенного ниже кода, найдите асимптотику:
int func(vector <int> arr) {
    int n = arr.size();
    int max1 = INT_MIN, pos1 = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] > max1) {
            max1 = arr[i];
            pos1 = i;
        }
    }
    int max2 = INT_MIN, pos2 = -1;
    for (int i = 0; i < n; i++) {
        if (i == pos1) continue; 
        if (arr[i] > max2) {
            max2 = arr[i];
            pos2 = i;
        }
        return max2;
    }

1) O(1)
2) O(log(n))
3) O(n)
4) O(n^2)

 

Выберите правильный ответ, либо введите его в поле ввода

Комментарий учителя