Измерение наихудшей сложности алгоритма
Обозначение Big-O измеряет сложность алгоритма наихудшего случая. В нотации Big-O n представляет количество входов. Вопрос, задаваемый Big-O, звучит так: «Что произойдет, когда n приблизится к бесконечности?»
На рисунке ниже показаны некоторые распространенные нотации Big-O:
O (1) не изменяется по отношению к входному пространству. Следовательно, O (1) называется постоянным временем. Пример O (1):
function exampleConstantFunc(n) {
return n*n;
}
O (n) - это линейное время и применяется к алгоритмам, которые должны выполнять n операций в наихудшем сценарии. Это простой базовый цикл, в котором мы выполняем операции с постоянным временем. Пример O (n):
function exampleLinear(n) {
for (var i = 0 ; i < n; i++ ) {
console.log(i)
}
}
Логарифмическая функция времени - это функция, в которой время выполнения пропорционально логарифму размера ввода. Рассмотрим следующий пример:
function log(n) {
for (let i = 1; i > n; i*=2) {
const result = i;
console.log(result);
}
}
Мы можем видеть, что в любой данной итерации значение i = 2i, поэтому на n-й итерации значение i = 2n. Кроме того, мы знаем, что значение i всегда меньше размера самого цикла (N). Отсюда мы можем вывести следующий результат: 2 [^ n] ‹N log (2 [^ n])‹ log (N) n ‹log (N)
Из предыдущего кода мы видим, что количество итераций всегда будет меньше, чем размер журнала ввода. Следовательно, наихудшая временная сложность такого алгоритма будет O (log (n)). Эффективность логарифмических временных сложностей очевидна при больших входных данных, таких как миллион элементов.
С помощью алгоритмов квадратичного времени мы вошли в темную сторону временной сложности. Как следует из названия, размер входных данных квадратично влияет на время работы алгоритма. Один из распространенных примеров - вложенные циклы:
for (int i = 0; i <n; i += c) {
for (int j = 0; j < n; j += c) {
// some O(1) expressions
}
}
Как видно из предыдущего примера, для i = 0 внутренний цикл выполняется n раз, то же самое для i = 1, i = 2 и т. Д. Внутренний цикл всегда выполняется n раз и не зависит от значения n, поэтому временная сложность алгоритмов составляет O (n 2).
Полиномиальное время (O (n ^ n))
Полиномиальная временная сложность - это временная сложность работы алгоритмов, которая имеет порядок n k. Алгоритмы с квадратичным временем - это определенные типы алгоритмов с полиномиальным временем, где k = 2. Вот простой пример такого алгоритма:
for (int i = 0; i <n; i += c) {
for (int j = 0; j < n; j += c) {
for (int k = 0; k < n; k += c) {
// some O(1) expressions
}
}
}
Как видите, этот пример является лишь продолжением примера в квадратичном временном разрезе. Наихудшая сложность этого случая - O (n ^ 3).
Представим сложность алгоритма как f (n). n представляет количество входов, f (n) time представляет необходимое время, а f (n) space представляет собой пространство (дополнительную память), необходимое для алгоритма. Цель анализа алгоритма - понять эффективность алгоритма путем вычисления f (n). Однако вычислить f (n) может быть непросто. Нотация Big-O предоставляет фундаментальные правила, которые помогают разработчикам вычислять f (n).
Правило коэффициента: избавьтесь от констант
Давайте сначала рассмотрим правило коэффициентов - самое простое для понимания правило. Он просто требует, чтобы вы игнорировали любые константы, не связанные с размером ввода. Коэффициенты в Big-O незначительны при больших размерах входных данных. Следовательно, это наиболее важное правило нотации Big-O.
Если f (n) равно O (g (n)), то kf (n) равно O (g (n)) для любой константы k ›0.
Это означает, что и 5f (n), и f (n) имеют одинаковую нотацию Big-O для O (f (n)). Вот пример блока кода с временной сложностью O (n):
function a(n){
var count =0;
for (var i=0;i<n;i++){
count+=1;
}
return count;
}
В этом блоке кода f (n) = n. Это потому, что он добавляет к счету n раз. Следовательно, эта функция имеет временную сложность O (n):
function a(n){
var count =0;
for (var i=0;i<5*n;i++){
count+=1;
}
return count;
}
В этом блоке f (n) = 5n. Это потому, что он работает от 0 до 5n. Однако в первых двух примерах используется нотация O (n) в формате Big-O. Проще говоря, это потому, что если n близко к бесконечности или другому большому числу, эти четыре дополнительные операции бессмысленны. Он собирается повторить это n раз. Любыми константами в нотации Big-O можно пренебречь.
Правило суммы: сложите большие суммы вместе
Правило сумм интуитивно понятно - можно добавить временные сложности. Представьте себе главный алгоритм, который включает два других алгоритма - нотация Big-O этого главного алгоритма представляет собой просто сумму двух других нотаций Big-O.
Если f (n) равно O (h (n)) и g (n) равно O (p (n)), то f (n) + g (n) равно O (h (n) + p ( п)).
Важно не забыть применить правило коэффициентов после применения этого правила. Следующий блок кода демонстрирует функцию с двумя основными циклами, временные сложности которых необходимо рассматривать независимо, а затем суммировать:
function a(n){
var count =0;
for (var i=0; i<n; i++){
count+=1;
}
for (var i=0; i<5*n; i++){
count+=1;
}
return count;
}
В этом примере в строке 4 f (n) = n, а в строке 7 - f (n) = 5n. В результате получается 6n. Однако при применении правила коэффициентов конечный результат O (n) = n.
Правило продукта: умножайте большие суммы
Правило продукта просто устанавливает, как можно умножить большие суммы.
Если f (n) равно O (h (n)) и g (n) равно O (p (n)), то f (n) g (n) равно O (h (n) p (n) ).
Следующий блок кода демонстрирует функцию с двумя вложенными циклами for, для которых применяется правило продукта:
function (n){
var count =0;
for (var i=0; i<n; i++){
count+=1;
for (var i=0; i<5*n; i++){
count+=1;
}
}
return count;
}
В этом примере f (n) = 5n * n, потому что строка 7 выполняется 5n раз, всего n итераций. Таким образом, получается всего 5n ^ 2 операций. Применяя правило коэффициентов, получаем, что O (n) = n ^ 2
Правило полиномов: большое О в степени k
Правило полиномов гласит, что полиномиальные временные сложности имеют обозначение Big-O той же полиномиальной степени. Математически это выглядит следующим образом:
Если f (n) - многочлен степени k, то f (n) равен O (n ^ k). В следующем блоке кода есть только один цикл for с квадратичной временной сложностью:
function a(n){
var count =0;
for (var i=0; i<n*n; i++){
count+=1;
}
return count;
}
В этом примере f (n) = n ^ 2, потому что в строке 4 выполняется n * n итераций.
Теперь, когда мы начали этот разговор, большинство типов временной сложности, которые мы обсуждали здесь до сих пор, относятся к типу O (n ^ k). Например, это постоянная временная сложность для n = 1, тогда как это квадратичная сложность для k = 2. Концепция полиномиальной временной сложности подводит нас к классу задач, которые определяются на основе сложности их решений.
Это типы занятий:
- P: любая проблема, которая может быть решена за полиномиальное время O (n ^ k).
- НП: любая проблема, которую можно проверить за полиномиальное время. Могут существовать проблемы (например, решение судоку), которые можно решить за недетерминированное полиномиальное время. Если решение этих проблем может быть проверено за полиномиальное время, тогда проблема классифицируется как проблема NP-класса. Задачи класса NP являются надмножеством задач класса P.
- NP-Complete: любая проблема NP, которая может быть уменьшена как функция другой проблемы NP за полиномиальное время, может быть классифицирована как проблема NP-Complete. Это означает, что если мы знаем решение определенной проблемы NP, то решение другой проблемы NP может быть получено за полиномиальное время.
- NP-Hard: проблема может быть классифицирована как NP-Hard проблема (H), если существует NP-полная проблема, которая может быть сведена к H за полиномиальное время.
В большинстве реальных сценариев мы столкнемся с множеством проблем P и NP, классический пример проблемы класса NP - коммивояжер, когда продавец хочет посетить n городов, чтобы начать и закончить. его поездка из его дома. С ограниченным количеством бензина и верхним пределом общего количества миль, которое может проехать, сможет ли продавец посетить все города, не исчерпав бензин?
До сих пор мы видели несколько довольно простых примеров: все они имеют один цикл или вложенные циклы. Однако часто будут сценарии, в которых нам придется обрабатывать несколько циклов / вызовов функций / ветвей, происходящих из одного и того же алгоритма. Давайте посмотрим на примере, как мы можем вычислить сложность в этом случае.
Общая сложность этого кода будет суммированием сложности обоих разделов. Итак, в этом случае общая сложность будет O (n + log n), что асимптотически будет O (n).
Здесь сложность наихудшего случая будет определяться худшим из двух ветвей, которым будет O (n), но сложность наилучшего случая будет O (log (n)).
Хотя наш метод выполняет только некоторые операции O (1), он постоянно изменяет входные данные и вызывает себя до тех пор, пока размер входного массива не станет нулевым. Итак, наш метод выполняется n раз, что составляет общую временную сложность O (n).
