Использование математики для измерения эффективности кода

Идея позади

Большая нотация O — это язык, который мы используем, чтобы говорить о том, сколько времени требуется алгоритму для выполнения. Это то, как мы сравниваем эффективность различных подходов к проблеме.

С помощью большой нотации O мы выражаем время выполнения в терминах насколько быстро оно растет по отношению к входным данным, когда входные данные становятся сколь угодно большими.

  1. насколько быстро увеличивается время выполнения. Трудно определить точное время выполнения алгоритма. Это зависит от скорости процессора, от того, что еще работает на компьютере и т. д. Поэтому вместо того, чтобы говорить непосредственно о времени выполнения, мы используем нотацию с большой буквой O, чтобы говорить о том, как быстро растет время выполнения.
  2. относительно входных данных. Если бы мы измеряли время выполнения напрямую, мы могли бы выразить нашу скорость в секундах. Поскольку мы измеряем насколько быстро растет время выполнения, нам нужно выразить нашу скорость в терминах… чего-то еще. В нотации Big O мы используем размер входных данных, который мы называем «n». Таким образом, мы можем сказать, что время выполнения растет «порядка размера входных данных» (O(n)) или «порядка квадрата размер ввода» (O(n²)).
  3. поскольку входные данные становятся произвольно большими. В нашем алгоритме могут быть шаги, которые кажутся дорогостоящими, когда n мало, но в конечном итоге затмеваются другими шагами, когда n становится огромный. Для анализа большого O нас больше всего заботит то, что растет быстрее всего по мере роста входных данных, потому что все остальное быстро затмевается, когда n становится очень большим. (поэтому он называется «асимптотическим анализом».)

Некоторые примеры

1.

void printItem(int items[], int n){
    cout<<items[0];
}

Вышеупомянутая функция будет выполняться за время O(1). Входным вектором может быть 1 элемент или 100 элементов, но для этой функции все равно потребуется всего один «шаг».

Примечание: оператор print или cout выполняется за время O(1).

2.

void printItems(int items[], int n){
    for(int i=0;i<n;i++){
        cout<<items[i]<<" ";
    }
}

Эта функция выполняется за время O(n) (или «линейное время»), где n — количество элементов в векторе. Если в векторе 10 элементов, мы должны напечатать 10 раз. Если в нем 10 000 элементов, нам нужно напечатать 10 000 раз.

3.

void printSubItems(int items[], int subItems[], int n){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<items[i]<<" "<<subItems[j]<<endl;
        }
    }
}

Здесь мы вкладываем два цикла. Если наш вектор состоит из n элементов, наш внешний цикл выполняется n раз, а наш внутренний цикл выполняется n раз для каждой итерации внешнего цикла, что дает нас n² всего отпечатков. Таким образом, эта функция выполняется за время O(n²) (или «квадратичное время»). Если в векторе 10 элементов, нам нужно напечатать 100 раз. Если в нем 1000 элементов, нам нужно напечатать 1 000 000 раз.

Отбросьте константы

Когда вы вычисляете большую O-сложность чего-то, вы просто выбрасываете константы. Например:

void printItemsTwice(int items[], int n)
{
    for (int i=0;i<n;i++) {
        cout << items[i] << endl;
    }

    // once more
    for (int i=0;i<n;i++) {
        cout << items[i] << endl;
    }
}

Это O(2n), которое мы просто называем O(n).

Если временная сложность равна O(1+n/2+100), мы можем просто назвать ее O(n).

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

Короче говоря, мы можем сказать, что можно отбросить менее значимые термины, чтобы получить окончательную сложность. Например:

  1. O(n³+50*n²+10000) is O(n³)
  2. O(n*(n+1)/2) is O(n²)

Обычно мы говорим о «худшем случае».

bool isAllEven(int ar[], int n)
{
    for (int i=0;i<n;i++) {
        if (a[i]%2==1) {
            return false;
        }
    }

    return true;
}

Здесь у нас может быть 100 элементов в нашем массиве, но первый элемент может быть нечетным, и в этом случае мы вернемся всего за 1 итерацию нашего цикла.

В общем случае мы бы сказали, что это O(n) времени выполнения, и подразумевалась бы часть «наихудшего случая». Но чтобы быть более конкретным, мы могли бы сказать, что это в худшем случае O(n) и в лучшем случае O(1) времени выполнения. Для некоторых алгоритмов мы также можем сделать строгие утверждения о времени выполнения в «среднем случае».

Сложность пространства

Иногда мы хотим оптимизировать использование меньшего объема памяти вместо (или в дополнение к) использования меньшего времени. Говорить о стоимости памяти (или «пространственной сложности») очень похоже на разговор о стоимости времени. Мы просто смотрим на общий размер (относительно размера входных данных) любых новых переменных, которые мы выделяем.

void example(int n)
{
    for (int i = 0; i < n; i++) {
        cout << "Hello world" << endl;
    }
}

Приведенная выше функция занимает O(1) пространства (мы используем фиксированное число переменных) и O(n) временной сложности.

vector<int> copy(int n)
{
    vector<string> temp;
    for (int i = 0; i < n; i++) {
        temp.push_back(i+1);
    }
    return temp;
}

Приведенная выше функция занимает O(n) пространства (размер временного вектора) и O(n) времени.

Обычно, когда мы говорим о сложности пространства, мы имеем в виду дополнительное пространство, поэтому мы не учитываем пространство, занимаемое входными данными.

Иногда существует компромисс между экономией времени и экономией места, поэтому вам нужно решить, для чего вы оптимизируете.

Проблемы с анализом Big O

Асимптотический анализ — мощный инструмент, но используйте его с умом.

  1. Big O игнорирует константы, но иногда константы имеют значение. Если у нас есть сценарий, выполнение которого занимает 100 часов, оптимизация, которая делит время выполнения на 5, может не повлиять на большой O, но все равно сэкономит вам 80 часов ожидания.
  2. Иногда оптимизация времени или пространства негативно влияет на удобочитаемость или время кодирования.

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