Определение

Big O показывает верхнюю границу зависимости между входными параметрами функции и количеством операций, которые выполнит процессор.

Типы сложности

• Комбинаторная сложность — миниальное число элементов для реализации алгоритма в виде вычислительного устройства
• Описательная сложность — длина описания алгоритма на формальном языке
• Вычислительная сложность — количество элементарных операций, испольняемых алгоритмов для неких входных данных

Суть

При передаче данных файлов по сети: Если считать файлы как биты, то при передаче данных через Интернет получается, что чем больше бит, тем больше времени требуется для передачи.
Линейная зависимость O(N). (Прямая y=x+k)

Если скорость передачи не зависит от объема (например если весь объем ифнормации перенести (перевезти) физически, например на самолете), то это
Линейная зависимость O(1). (Прямая y=1) В данном случаее 1 — обозначение, что что-то происходит. Если ничего не происходит, то сложность O(0), Прямая

Примеры

Рекурсивная функция — быстродействие O(N)

int sum(int n) {
    if (n == 1) return 1;
    return n + sum(n - 1);
}

Использование цикла с вызовом вспомогательной функции (O(N))

int pairSumSeq(int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) { 
        sum+= pairSum(i, i+1);
    }
}

int pairSum(int a, int b) { // Сложность: O(1)
    return a + b;
}

O(N) поскольку зависимость линейная: чем больше N тем больше итераций (линейно).

Верхняя граница (отбрасывание констант)

Big O оценивает скорость роста, т.е. нет смысла в оценке скорости выполнения операции, а значит O (N) аналогичен O (2N), а значит есть смысл подобные константы отбрасывать.

Неважная сложность

Пример на основе сложости O (N^2 + N)

1. N — не является константой
2. O (N^2 + N^2) = O (N^2) (из-за отбрасывания констант)
3. N^2 > N (значительно больше), а значит N не влияет на темп роста функции, т.е. её сложность является неважной
4. O(N^2 + N) = O (N^2)

Примеры

1. O (N^2 + N) = O (N^2)
2. O (N + log N) = O(N) (потому что logN <<< N)
3. $$O (5 2^N + 10 N^100) = O (2^N) (степенная функция 2^N растет гораздо быстрее чем N^100)
4. O (N^2 + B) = O (N^2 + B) (поскольку ничего не известно о B)

Сложение и умножение

Сложение

for (int a : arrA) {
    print(a);
}

for (int b : arrB) {
    print(b);
}

Здесь сложность O (A + B) — последовательность действий — сложение

Умножение

for (int a : arrA) {
    for (int b : arrB) {
        print(a + ", " + b);
    }
}

Здесь сложность O (A * B) — повторение повторений — умножение

Сложность O (log N)

Бинарный поиск в отсортированном массиве

1. Берем середину массива
2. Число меньше середины идем в левый подмассив, больще — в правый
3. Повторяем тоже самое для подмассива
4. Конец, когда нашли искомое или длина массива станет 1

Т.е. количество операций — logN (по основанию 2). Поскольку константы не играют роли, получается сложность O(logN)

Т.е. для алгоритма, где на каждой итерации берется половина элементов, сложность будет включит O (log N). Включить — значит, что log N будет присутствовать в формуле сложности (например N log N, и т.п.)

Особые случаи

При сортировке строк используется цикл, но сравнение строк — не однотактовая операция, таким образом сортировка строки — O (L log L).
Если необходимо так же отсортировать массив строк, то сложность будет O (N L log L + L N log N) = O (L N * (log L + log N))

Источники

• Оценка сложности алгоритма. Сложность алгоритмов. Big O, Большое О — YouTube
• 1. Алгоритмы и структуры данных. Введение | Технострим — YouTube