Обозначение O-большое: введение для начинающих разработчиков

Обозначение O-большое – один из самых базовых инструментов информатики для анализа временной и пространственной сложности алгоритма.

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

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

Что будет рассмотрено в данной статье:

• Что такое обозначение O-большое?
• Что такое временная и пространственная сложность?
• Распространенные разновидности обозначения O-большое
• Асимптотический анализ: как определить сложность алгоритма
• Примеры кода для обозначений O-большое
• Шпаргалка по обозначению O-большое

Что такое обозначение O-большое?

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

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

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

Что такое временная и пространственная сложность?

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

Сложность – это приблизительная мера эффективности алгоритма, связанная с каждым написанным вами алгоритмом. Это то, о чем должны знать все программисты.

Есть два вида сложности: временная и пространственная. Временная сложность и пространственная сложность – это, по сути, аппроксимации того, сколько времени и сколько места потребуется алгоритму для обработки определенных входных данных.

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

• Не становится ли алгоритм внезапно невероятно медленным при увеличении размера входных данных?
• Сохраняет ли он быстрое время выполнения при увеличении размера входных данных?

Лучший случай – обозначается как Омега-большое или Ω(n).

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

Средний случай – обозначается как Тета-большое или Θ(n)

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

Худший случай – обозначается как O-большое или O(n)

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

Разработчики обычно выбирают наихудший сценарий, O-большое потому, что вы не ожидаете, что ваш алгоритм будет запускаться в лучших или даже средних условиях. Это позволяет вам делать аналитические заявления, такие как «ну, в худшем случае мой алгоритм масштабируется так быстро».

Распространенные разновидности обозначения O-большое

Эти разновидности обозначения O-большое не единственные, но с ними вы, скорее всего, будете сталкиваться часто.

O(1) – постоянная временная сложность

O(1) означает постоянное время выполнения, что означает, что независимо от размера входных данных алгоритм будет иметь одинаковое время выполнения.

Пример:

Массив: вставка или получение элемента

O(log n) – логарифмическая временная сложность

O(log n) означает, что время увеличивается линейно, когда n растет экспоненциально. Таким образом, если для вычисления 10 элементов требуется 1 секунда, то для вычисления 100 элементов потребуется 2 секунды, и так далее. Сложность равна O(log n), когда мы используем алгоритмы «разделяй и властвуй», например, бинарный поиск.

Пример:

Двоичное дерево: вставка или получение элемента

O(n) – линейная временная сложность

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

Пример:

Дерево: поиск в глубину (DFS) дерева

O(n²) – квадратичная временная сложность

По мере увеличения количества элементов в вашем списке время, необходимое для работы вашего алгоритма, будет увеличиваться экспоненциально.

Пример:

Алгоритм сортировки: пузырьковая сортировка и сортировка вставками.

Асимптотический анализ: как определить сложность алгоритма

Как найти O-большое алгоритма

Если на собеседовании вас просят определить сложность O-большое алгоритма, вот общее правило:

• отбросьте ведущие константы;
• игнорируйте члены более низкого порядка.

Пример: найдите сложность O-большое алгоритма с временной сложностью 3n³ + 4n + 2.

Это упрощается до O(n³).

Как найти временную сложность алгоритма

При расчете временной сложности алгоритма вам необходимо выполнить три шага:

1. перечислите все основные операции в коде;
2. подсчитайте, сколько раз каждая из них была выполнена;
3. суммируйте все подсчеты, чтобы получить формулу.

Простой пример, который измеряет временную сложность цикла for размером n:

#include <iostream>
using namespace std;
int main()
{
   int n = 10;    // O(1)
   int sum = 0;   // O(1)
   for (int i=0; i<n; i++)
       sum+=2;    // O(1)
   cout << sum;   // O(1)
   return 0;
}

Сначала разделите код на отдельные операции, а затем вычислите, сколько раз они выполняются, что будет выглядеть так:

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

Временная сложность = 1+1+1+(n+1)+n+n+1=3+(n+1)+2n+1=>3n+5

Общие советы по асимптотическому анализу:

• каждый раз, когда список или массив повторяется x раз, сложность, скорее всего, равна O(n);
• когда вы видите задачу, в которой обрабатываемое количество элементов каждый раз уменьшается вдвое, скорее всего, временная сложность будет равна O(log n);
• всякий раз, когда у вас есть единожды вложенный цикл, алгоритм, скорее всего, имеет квадратичную временную сложность.

Полезные формулы для расчета временной сложности алгоритма:

Примеры кода для обозначений O-большое

О(1)

 void printFirstItem(const vector<int>& items)
{
    cout << items[0] << endl;
}

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

О(n)

void printAllItems(const vector<int>& items)
{
    for (int item : items) {
        cout << item << endl;
    }
}

Данная функция выполняется за время O(n) (или «линейное время»), где n – количество элементов в векторе. Если в векторе 10 элементов, необходимо 10 операций печати. Если в нем 1000 элементов, нам придется выполнить 1000 операций печати.

O(n²)

void printAllPossibleOrderedPairs(const vector<int>& items)
{
    for (int firstItem : items) {
        for (int secondItem : items) {
            cout << firstItem << ", " << secondItem << endl;
        }
    }
}

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

Шпаргалка по обозначению O-большое

Теги