Временная сложность Big-O - важный предмет в информатике / разработке программного обеспечения, который позволяет нам измерять временную и пространственную сложность нашего кода. Эта информация помогает нам оптимизировать и определять масштабируемость нашего кода, тем самым повышая эффективность кода.
В этой статье я рассмотрю концепцию временной сложности Big-O и объясню основные временные сложности, которые должен знать каждый компьютерный ученый / инженер-программист. Я бы также обсудил некоторые правила вычисления временной сложности Big-O.
Содержание
- Что такое временная сложность?
- O (1) - постоянная сложность времени
- O (N) - линейная временная сложность
- O (log (n)) - логарифмическая временная сложность
- O (N²) - квадратичная временная сложность
- O (2 ^ N) - экспоненциальная временная сложность
- Правила временной сложности Big-O
- Заключение
Что такое время - сложность?
Почему я должен знать о Big-O?
Big-O полезен для определения скорости вашего кода, если вы когда-либо думали, что ваш код работает слишком медленно или, возможно, ваш код работает отлично, но он не выполняется так быстро, как другие более длинные. Временная сложность вашего кода может объяснить, почему он выполняется именно в то время, которое он выполняет.
Обозначение Big-O - это типичный метод изображения производительности или сложной природы алгоритма в компьютерных науках, обозначение n представляет количество входов. Он используется как индикатор для проверки эффективности вашего кода и возможности его улучшения. В этой статье я попытаюсь разбить каждую временную сложность и объяснить, как они работают в реальной жизни, чтобы в конце этой статьи вы могли проанализировать фрагменты кода и указать, какой из них попадает в какую временную сложность. .
O (1) - постоянная сложность времени
CTC описывает алгоритм, который всегда будет выполняться в одно и то же время (или пространство) независимо от размера входных данных. В JavaScript это может быть так же просто, как доступ к определенному индексу в массиве:
var array = [1, 2, 3]; array[0] // This is a constant time look-up
Не имеет значения, имеет ли массив длину 3 или 30 000, поиск определенного индекса в массиве займет такое же время, поэтому функция имеет поиск в постоянном времени. Рассмотрим другой пример.
function ctcExample(n) {
return n*n;
}
В этом втором примере функция ctcExample принимает один параметр и возвращает его квадрат, независимо от размера этого параметра, эта функция всегда будет занимать одинаковое количество времени для выполнения.
Последний пример, если мы сложим листы бумаги с написанными на них именами, разложенными по столу, и я скажу вам выбрать любое имя из таблицы, вы можете просто взять первое имя, которое вы видите, из таблицы, без ударения, это поиск по постоянному времени.
O (N) - линейная временная сложность
Сложность линейного времени описывает алгоритм, сложность которого будет возрастать прямо пропорционально размеру входных данных. Это относится к алгоритмам, которые должны выполнять «n' операций в худшем случае». В качестве надежного ориентира лучше всего пытаться поддерживать работу ваших функций ниже или в этом диапазоне временной сложности, но, очевидно, это не всегда будет возможно.
function ltcExample(array) {
for (var i = 0; i < array.length; i++) {
console.log(array[i]);
}
}
В приведенном выше примере будет линейный поиск по времени, поскольку функция просматривает каждый индекс в массиве один раз.
В нашем примере время поиска связано с размером нашего ввода, потому что мы будем перебирать каждый элемент в массиве. Следовательно, чем больше ввод, тем больше времени требуется для выполнения функции. Обратите внимание, что если бы у массива был только один индекс, у него был бы постоянный поиск по времени.
Чтобы прояснить ситуацию, предположим, что у нас все еще были листы бумаги на столе, и я попросил вас взять лист бумаги и назвать написанное на нем имя. Вам придется просматривать каждый листок бумаги, называя имена. А теперь подумайте, если бы этот стол был очень длинным, заполненным множеством крошечных листов бумаги, это потенциально могло занять много времени. Ваш поиск напрямую связан с количеством бумажек на столе.
O (log (n)) - логарифмическая временная сложность
Сложность логарифмического времени описывает алгоритм, время выполнения которого пропорционально логарифму размера ввода. Давайте медленно пройдемся по этому вопросу.
function logtcExample(array) {
for (var i = 1; i < array.length; i = i * 2) {
//don't initialize i as zero, seriously don't!
console.log(array[i]);
}
}
В приведенном выше примере будет логарифмический поиск по времени, так как функция будет искать только определенные части массива.
Из примера видно, что в любой данной итерации значение i равно 2i (i = 2i), поэтому на n-й итерации (где n = array.length) значение i равно 2n ( i = 2n). Кроме того, мы знаем, что значение i всегда меньше размера самого ввода (i ‹N).
поэтому мы можем сделать следующие выводы:
2n ‹N
log (2n)‹ log (N)
n ‹log (N)
Из предыдущего кода мы видим, что количество итераций всегда будет меньше, чем логарифм размера ввода. Следовательно, наихудшая временная сложность такого алгоритма будет O (log (n)).
Эффективность логарифмических временных сложностей очевидна при больших входных данных, таких как миллион элементов.
И, наконец, давайте снова рассмотрим наш пример листы бумаги на столе, но на этот раз все части расположены в стопки в алфавитном порядке, если я сказал вам выбирать каждый кусок, имя которого начинается с D, за которым следует a. На этот раз вам не нужно перебирать все элементы на столе, но это оказалось не так просто, как выбрать одну наугад.
O (N²) - квадратичная временная сложность
Квадратичная временная сложность описывает алгоритм, время выполнения которого прямо пропорционально квадрату размера входных данных (подумайте о линейном, но возведенном в квадрат). В нашем коде эта временная сложность будет возникать всякий раз, когда мы вкладываем несколько итераций в данные.
function qtcExample(array) {
for (var i = 0; i < array.length; i++) {
var item = array[i];
if (array.slice(i + 1).indexOf(item) !== -1) {
return true;
}
}
return false;
};
В приведенном выше примере мы обращаемся к нашему массиву дважды (без использования двух циклов for). Цикл for выполняет итерацию по каждому элементу в массиве, и на каждой итерации оператор проверяет массив, чтобы найти элемент indexOf. Следовательно, это дает квадратичную временную сложность.
Из примера, который мы видим для каждой итерации, внутренний оператор выполняется n раз, поэтому в конце внешнего цикла количество итераций будет равно n². Следовательно, сложность времени для наихудшего случая такого алгоритма будет O (n²).
Вернемся к нашему примеру с листками бумаги на столе. Если на этот раз части сложены стопкой, и я просил вас выбрать первую часть в стопке, удалите все части, первая буква которых похожа на первую букву той, которую вы выбрали. Вам придется перебирать каждый лист бумаги на столе, удаляя похожие по ходу дела. После того, как все похожие будут удалены, вам придется повторять процесс для следующего фрагмента, который вы выберете, и так далее, пока не дойдете до конца стопки. Я уверен, что ты понял сейчас.
O (2 ^ N) - экспоненциальная временная сложность
Экспоненциальная временная сложность обозначает алгоритм, рост которого удваивается с каждым добавлением к входному набору данных. Если вам известны другие модели экспоненциального роста, это работает примерно так же. Временная сложность начинается очень неглубоко, и до конца возрастает со все возрастающей скоростью.
function etcFibonacci(number) {
if(number <= 1) return number;
return etcFibonacci(number - 2) + etcFibonacci(number - 1);
}
В этом примере реализована рекурсия, чтобы объяснить, как функция может выполнять поиск по экспоненциальному времени. Здесь рекурсивная реализация будет проходить через каждое число от number до нуля. Он будет делать это дважды (один раз для каждого рекурсивного вызова), пока не достигнет базового случая оператора if. Поскольку количество рекурсивных вызовов напрямую связано с параметром number, легко увидеть, как это время поиска быстро вырастет из-под контроля.
Правила большой сложности
Правила вступают в силу, когда вы пытаетесь определить сложность алгоритма. В случае большого (модульного) фрагмента кода, который обладает разной сложностью в разные промежутки времени, вам может потребоваться просмотреть каждую строку вашего кода, чтобы определить, является ли он O (1), O (n) и т. Д., А затем вернуть полученные результаты. Однако вычислить эти временные сложности может быть непросто. Поэтому нам предоставили пару правил, которые упростят процесс расчета. Некоторые из этих правил включают:
- Рассмотрим худший случай
- Правило коэффициента (удаление констант)
- Правило суммы
- Правило продукта
- Отбросить недоминант
Рассмотрим худший случай
При вычислении Big O рекомендуется всегда учитывать наихудший сценарий. Например, при поиске в массиве элемента «x» (см. Пример бумаги O (n)) «x» может быть первым или последним элементом. Поскольку мы не уверены в местонахождении «x», мы должны учитывать размер массива и предполагать O (n) в этом случае.
Правило коэффициента
Это правило требует, чтобы мы игнорировали любую константу, которая не связана с размером нашего входного размера. В случаях, когда есть более сложные алгоритмы, чем O (1), мы обязаны удалить константу. Например, давайте рассмотрим этот блок кода:
function x(n){
var counter =0;
for (var i = 0; i < 5+n; i++){
count += 1;
}
return count;
}
Этот пример имеет сложность O (5 + n), потому что цикл имеет линейную сложность от 0 до 5 + n. В этом случае константа «5» не влияет напрямую на размер входных данных и может оказаться несущественной. Следовательно, в этом случае мы можем отбросить 5, сделав временную сложность O (n).
Правило суммы
Это правило позволяет нам выполнять арифметические сложения для временных сложностей. Если у нас есть алгоритм, состоящий из двух шагов (меньшие внутренние алгоритмы). Чтобы получить временную сложность этих алгоритмов, мы просто суммируем сложности внутренних алгоритмов. Например, давайте рассмотрим этот блок кода:
function x(n){
var counter =0;
for (var i = 0; i < n; i++){
count += 1;
}
for (var i = 0; i < 5*n; i++){
count += 1;
}
return count;
}
В этом примере первый цикл имеет временную сложность O (n), а второй цикл имеет временную сложность O (5n). Следовательно, Big O функции x равен O (n + 5n) и приводит к O (6n). Однако мы всегда должны применять правило коэффициентов и, используя сумму, окончательная сложность функции x равна O (n) = n.
Правило продукта
Это правило позволяет нам выполнять арифметическое умножение на временных сложностях. Это можно применить аналогично правилу суммы, но в разных сценариях. Например, давайте рассмотрим этот блок кода:
function x(n){
var counter =0;
for (var i = 0; i < n; i++){
count += 1;
for (var i = 0; i < 5*n; i++){
count += 1;
}
}
return count;
}
В этом примере первый цикл имеет квадратичную временную сложность O (n), а второй цикл имеет временную сложность O (5n). Поскольку 5n выполняется всего n итераций, Big O функции x равен O (5n * n) и приводит к O (5n2). Применяя правило коэффициентов, окончательная сложность функции x равна O (n) = n2.
Отбросить недоминант
Это правило аналогично правилу коэффициентов, оно требует от нас использования недоминантного члена в случаях, когда невозможно определить определенную временную сложность и нет константы, которую можно было бы отбросить. Например, давайте рассмотрим этот блок кода:
function x(n){
var counter =0;
for (var i = 0; i < n; i++){
console.log(n);
}
for (var i = 0; i < n; i++){
count += 1;
for (var i = 0; i < 5*n; i++){
count += 1;
}
}
return count;
}
В этом примере есть два цикла, одиночный и вложенный, один имеет временную сложность O (n), а второй цикл - временную сложность O (n2). Следовательно, Большой O функции x равен O (n + n²). В этом случае мы отбрасываем O (n) и оставляем O (n2), так как это более важно, поскольку оказывает более сильное влияние на производительность функции по сравнению с O (n).
Заключение
Мы подошли к концу, это было напряженно (по крайней мере, для меня, чтобы написать). Если вы хотите улучшить свое понимание темы, воспользуйтесь шпаргалкой. Ваше здоровье.
