Обзор
Другие дали хорошие примеры диаграмм, таких как древовидные диаграммы. Простых примеров кода я не видел. Поэтому в дополнение к своему объяснению я предоставлю несколько алгоритмов с простыми операторами печати, чтобы проиллюстрировать сложность различных категорий алгоритмов.
Во-первых, вам нужно иметь общее представление о логарифме, которое вы можете получить из 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). Обратите внимание, что пост-операция цикла 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 раз. п / 2 = 1/2 * п. Мы игнорируем константу 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";
Резюме
Выше приведены несколько простых примеров и вариаций, которые помогут продемонстрировать, какие тонкие изменения могут быть внесены, которые на самом деле не меняют анализ. Надеюсь, это даст вам достаточно информации.
person
James Oravec
schedule
26.04.2016
< / а>
