В чем идея Big O?

Как узнать, насколько быстро работает наш алгоритм? Вот тут-то и пригодится нотация Big O. Давайте посмотрим, как это определяется в Google:

Теоретическая мера выполнения алгоритма, обычно необходимое время или память с учетом размера проблемы n, который обычно представляет собой количество Предметы. Неофициально, выражение некоторого уравнения f (n) = O (g (n)) означает, что оно меньше некоторого постоянного кратного g (n).

Вместо того, чтобы оценивать наш код такими словами, как «отлично», «хорошо» или «ужасно», мы можем иметь числовое представление для оценки производительности нашего кода.

Это может показаться немного математическим, но как только вы поймете концепцию, вам станет легче учиться!

Почему мы заботимся?

Почему нас вообще волнует, какой алгоритм лучше? Разве не должно быть лучшим решением то, что оно работает? Верно, но что, если мы работаем с огромным набором данных?

  1. Когда один алгоритм может сэкономить часы по сравнению с другим; для нас важно иметь возможность официально говорить о производительности нашего кода.

2. Существует так много способов решить одну и ту же проблему, что обсуждение большого числа полезно для обсуждения компромиссов между различными подходами к решению проблем.

3. Это также помогает нам понять, когда мы отлаживаем, потому что знание того, как работает среда выполнения, поможет нам определить неэффективный код в наших приложениях.

4. Вероятно, менее важная причина, но она часто встречается в интервью много!

Давайте рассмотрим две функции для сравнения

Предположим, мы хотим написать функцию, которая получает сумму всех чисел от 1 до некоторого числа n в Javascript. Давайте посмотрим на следующие две функции.

Обе функции делают одно и то же, но одна менее интуитивно понятна, да еще немного математической магии для второй!

За тем, как мы пришли ко второй функции, стоит математика, но это не основная тема этого блога, поэтому я не буду углубляться в ее обсуждение. Давайте продолжим основное внимание, которое будет оценивать и сравнивать эти два фрагмента кода.

Вероятно, мы могли бы сравнить эти две функции, измерив время выполнения.

Но, наверное, не лучшим образом ...

В чем проблема, если мы используем время для измерения скорости выполнения кода? Ну, разные компьютеры будут записывать разное время и / или измерения могут быть недостаточно точными.

Как узнать, какой код лучше?

Попробуем посчитать количество операций! давайте посмотрим на простую операцию с короткой строкой кода:

function addUpTo(n) {
return n * (n + 1)/2;
}

1 умножение, 1 сложение, 1 деление. Итак, независимо от размера n, у нас есть 3 простые операции. Давайте посмотрим на первый:

function addUpTo(n) {
let total = 0;
for (let i = 1; i<= n; i++){
   total += i;   
  }
}

Это не одна операция, это n добавлений и назначений по этой функции. когда мы смотрим на i ++, там есть дополнения и назначения. это n добавлений и n назначений по мере увеличения размера n.

Считать просто сложно! С ростом n количество операций растет пропорционально n.

Представьте Big O

Большое o - это просто способ формализовать сложный подсчет!

Это дает нам формальный способ говорить о том, что время выполнения алгоритмов растет по мере роста входных данных! Вот такая тенденция.

f (n) как вывод; n как ввод.

f(n) could be linear f(n) = n

по мере масштабирования n (вход) масштабируется и f (n) (время выполнения).

f(n) could be quadratic f(n) = n^²

по мере роста n (input) время выполнения f (n) квадратирует.

f(n) could be constant f(n) = 1

по мере роста n (input) он не влияет на время выполнения f (n), потому что время выполнения всегда константа, которую можно упростить до 1.

Нижняя линия

Вот суть этого блога:

Когда мы говорим о Big O, мы говорим о сценарии плохого, верхней границе времени выполнения.

По мере увеличения n это отражается на времени выполнения.

вернемся к нашим примерам ранее:

function addUpTo(n) {
return n * (n + 1)/2;
}

Тенденция имеет большой O, равный 1 O (1), это говорит нам о том, что по мере роста ввода функции время выполнения не отражается.

По сравнению со вторым,

function addUpTo(n) {
let total = 0;
for (let i = 1; i<= n; i++){
total += i;   
  }
}

происходит множество операций, числовые операции в конечном итоге отбрасываются на число, кратное n, скажем, 10n.

Одна вещь, которую мы хотим подчеркнуть, - это то, что нас не волнует погода, равная 5 или 10 градусам. По сути, они такие же, когда мы изобразили это на массивной диаграмме с большим размером входных данных. Мы заботимся только о порядке широты на графике, говоря словами, мы заботимся просто суетливо!

Я надеюсь, что эта статья поможет прояснить концепцию нотации Big O. Эта статья вдохновлена ​​одним из моих любимых инструкторов udemy, Кольтом Стилом, его курс называется Мастер-класс по алгоритмам JavaScript и структурам данных.

Если вам понравилось, хлопайте ниже!

Сказать привет! Instagram | Твиттер | Youtube | Facebook | LinkedIn