Понимание сложности Big O

Question

Мне сложно понять сложность времени.

Формальное определение Big O:

f(n) = O(g(n)) означает, что существуют положительные постоянные c и k, такие что 0 ≤ f(n) ≤ cg(n) для всех n ≥ k. Значения c и k должны быть фиксированными для функции f и не должны зависеть от n.

И наихудшая временная сложность сортировки вставки - O(n^2).

Я хочу понять, что здесь f(n), g(n), c и k случай вставки сортировки.

Answer 1

Объяснение

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

• Так что f - это функция, которая измеряет, сколько шаги вычисления, которые выполняет алгоритм.
• n - это размер ввода, например 5 для списка, подобного [4, 2, 9, 8, 2].
• g - это функция, с которой вы измеряете поэтому g = n^2, если вы проверяете O(n^2).
• c и k, сильно зависят от алгоритма Speci c и от того, как именно выглядит f.

---

Пример

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

public static void printAllEven(int n) {
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            System.out.println(i);
        }
    }
}

Сколько шагов он выполняет? Насколько глубоко мы должны go? Как насчет for (int i = 0; i < count; i++)? Это несколько операторов, которые выполняются в течение l oop. Как насчет i % 2? Можем ли мы предположить, что это «одиночная операция» ? На каком уровне один цикл процессора? Одна сборочная линия? Как насчет println(i), сколько шагов вычислений ему нужно, 1 или 5 или, может быть, 200?

Это не практично. Мы не знаем точное количество, мы должны абстрагироваться и сказать, что это постоянное количество шагов A, B и C, что нормально, так как оно выполняется в постоянное время.

---

После упрощения анализа мы можем сказать, что нас фактически интересует только то, как часто вызывается println(i).

Это приводит к наблюдению, что мы называем его точно n / 2 раз (так как много четных чисел от 0 до n.

Точная формула для f с использованием вышеуказанных констант даст что-то вроде

n * A + n * B + n/2 * C

Но так как константы на самом деле не играют никакой роли (они могут sh в c), мы могли бы просто проигнорировать это и упростить.

---

Теперь вам осталось доказать, что n / 2 находится в O(n^2) Например, сделав это, вы также получите конкретные числа для c и k. Пример:

n / 2 <= n <= 1 * n^2 // for all n >= 0

Таким образом, выбрав c = 1 и k = 0, вы подтвердили претензию Другие значения для c и k также работают, например:

n / 2 <= 100 * n <= 5 * n^2 // for all n >= 20

Здесь мы выбрали c = 5 и k = 20.

---

Вы можете сыграть в ту же игру с полной формулой и получить что-то вроде

n * A + n * B + n/2 * C
    <= n * (A + B + C)
    = D * n
    <= D * n^2 // for all n > 0

с c = D и k = 0.

Как видите, на самом деле это не играет никакой роли, константы просто вани sh в c.

Answer 2

В случае вставки sort f (n) - это фактическое количество операций, которые ваш процессор выполнит для сортировки. г (п) = п ² . Минимальные значения для c и k будут определяться реализацией, но они не так важны. Основная идея этой нотации Big-O состоит в том, что если вы удвоите размер массива, время, необходимое для работы сортировки вставкой, возрастет примерно в 4 раза (2 ² ). (Для сортировки вставки он может быть меньше, но Big-O дает только верхнюю границу)