Обзор
Другие приводили хорошие примеры диаграмм, такие как древовидные диаграммы. Я не видел простых примеров кода. Поэтому в дополнение к моему объяснению я приведу некоторые алгоритмы с простыми операторами печати, чтобы проиллюстрировать сложность различных категорий алгоритмов.
Во-первых, вам нужно иметь общее представление о логарифме, которое вы можете получить из https://en.wikipedia.org/wiki/Logarithm. Естествознание используют e и натуральный лог. Ученики-инженеры будут использовать log_10 (база 10 журналов), а ученые-программисты будут часто использовать log_2 (база 2 журналов), поскольку компьютеры работают на двоичном языке. Иногда вы можете увидеть сокращения натурального лога как ln(), инженеры обычно оставляют _10 выключенным и просто используют log(), а log_2 сокращается как lg(). Все типы логарифмов растут одинаковым образом, поэтому они разделяют одну и ту же категорию log(n).
Когда вы смотрите на примеры кода ниже, я рекомендую посмотреть O (1), затем O (n), затем O (n ^ 2). После того, как вы хорошо с ними, а затем посмотрите на других. Я включил чистые примеры, а также варианты, чтобы продемонстрировать, как незначительные изменения могут по-прежнему приводить к той же классификации.
Вы можете думать о O (1), O (n), O (logn) и т. Д. Как о классах или категориях роста. Некоторые категории займут больше времени, чем другие. Эти категории помогают нам упорядочить производительность алгоритма. Некоторые растут быстрее по мере роста n. Следующая таблица демонстрирует рост численно. В таблице ниже представьте log (n) как потолок log_2.
Примеры простых кодов различных больших категорий O:
O (1) - Примеры с постоянным временем:
Алгоритм 1 печатает привет один раз, и он не зависит от n, поэтому он всегда будет работать в постоянное время, поэтому он равен O(1).
print "hello";
Алгоритм 2 печатает привет 3 раза, однако он не зависит от размера ввода. Даже если n растет, этот алгоритм всегда будет печатать привет 3 раза. Это, как говорится 3, является константой, так что этот алгоритм также O(1).
print "hello";
print "hello";
print "hello";
O (log (n)) - Логарифмические примеры:
- Алгоритм 3 - действует как "log_2"
Алгоритм 3 демонстрирует алгоритм, который работает в log_2 (n). Обратите внимание, что операция post цикла for умножает текущее значение i на 2, поэтому i изменяется от 1 до 2, от 4 до 8, от 16 до 32 ...
.
for(int i = 1; i <= n; i = i * 2)
print "hello";
- Алгоритм 4 - действует как "log_3"
Алгоритм 4 демонстрирует log_3. Обратите внимание: i изменяется от 1 до 3 до 9 до 27 ...
for(int i = 1; i <= n; i = i * 3)
print "hello";
- Алгоритм 5 - действует как "log_1.02"
Алгоритм 5 важен, поскольку он помогает показать, что, пока число больше 1 и результат многократно умножается на самого себя, вы смотрите на логарифмический алгоритм.
for(double i = 1; i < n; i = i * 1.02)
print "hello";
O (n) - Примеры линейного времени:
Этот простой алгоритм выводит привет n раз.
for(int i = 0; i < n; i++)
print "hello";
Этот алгоритм показывает вариант, в котором он напечатает привет n / 2 раза. n / 2 = 1/2 * n. Мы игнорируем константу 1/2 и видим, что этот алгоритм равен O (n).
for(int i = 0; i < n; i = i + 2)
print "hello";
O (n * log (n)) - nlog (n) Примеры:
Думайте об этом как о комбинации O(log(n)) и O(n). Вложенность циклов for помогает нам получить O(n*log(n))
for(int i = 0; i < n; i++)
for(int j = 1; j < n; j = j * 2)
print "hello";
Алгоритм 9 аналогичен алгоритму 8, но каждый из циклов допускает изменения, которые все равно приводят к конечному результату O(n*log(n))
for(int i = 0; i < n; i = i + 2)
for(int j = 1; j < n; j = j * 3)
print "hello";
O (n ^ 2) - n в квадрате Примеры:
O(n^2) легко получается путем вложения стандартного для циклов.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
print "hello";
Как и алгоритм 10, но с некоторыми вариациями.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j = j + 2)
print "hello";
O (n ^ 3) - n в кубах Примеры:
Это похоже на алгоритм 10, но с 3 циклами вместо 2.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
print "hello";
Как и алгоритм 12, но с некоторыми вариациями, которые все еще дают O(n^3).
for(int i = 0; i < n; i++)
for(int j = 0; j < n + 5; j = j + 2)
for(int k = 0; k < n; k = k + 3)
print "hello";
Резюме
Выше приведено несколько простых примеров и вариаций, которые помогут продемонстрировать, какие тонкие изменения могут быть внесены, что действительно не меняет анализ. Надеюсь, это даст вам достаточно понимания.