В TLDR — Big O Notation рассматривается масштабирование алгоритма.
Как меняется скорость алгоритма по мере увеличения размера набора данных?
Идея нотации Big O была лучше всего понята мной в форме истории, в 2009 году почтовый голубь из Кейптауна по имени Уинстон вошел в историю, обойдя интернет-провайдера, доставив 4 ГБ данных на 75 км всего за 2 часа 6 минут и 57 секунд. В то же время по линии ADSL было отправлено всего 4% данных.
Нотация Big O смотрит на количество времени, которое что-то занимает, объем данных, которые у него есть.
Ниже перечислены другие сценарии
O(1)
Таким образом, голубю требуется столько же времени, чтобы передать 8 ГБ данных, сколько и 4 ГБ. Это известно как O(1) (то есть в лучшем случае). С точки зрения программирования, ваш проект может масштабироваться без каких-либо дополнительных усилий, он будет работать в обычном режиме, независимо от предоставленного ему объема (n).
O(n)
С другой стороны, скорость интернета и объем данных растут вместе,по мере того, как увеличивается объем передаваемых данных, увеличивается и объем времени, необходимого для выполнения задачи. Мы все сталкивались с этим в какой-то момент (большие файлы загружаются дольше, чем маленькие файлы). Это известно как O(n) с (n) в качестве переменной времени.
Эта переменная'n' может быть заменена тем, над чем вы работаете, она может представлять количество пользователей на сайте, количество запросов, отправляемых к конечной точке, или объем данных, извлекаемых из базы данных.
O(n²)
Примером O(n²) может быть цикл внутри цикла, также известный как вложенный цикл. Этот сценарий приведет к неэффективным алгоритмам, поскольку ваша нотация Big O будет быстро масштабироваться.
Это соответствует O(n²) на приведенной выше диаграмме.
Например
#Data
const data = [‘A’, ‘B’, ‘C’, ‘D’]
const data2 = [1, 2, 3, 4, 5]
#loops
for (let j =0; j < data2.length; j++){
for (let i = 0; i < data.length; i++) {
console.log(data[i] + data2[j])
}
}
#Results
A1
B1
C1
D1
A2
B2
etc...
O(n!) —задача коммивояжера
Последний вариант нотации Big O, о котором я хотел бы поговорить, это O(n!)
По мере масштабирования (n) решение становится непрактичным, этот пример хорошо виден в Задаче коммивояжера.
С учетом списка городов и расстояний между каждой парой городов, каков кратчайший возможный маршрут, который посещает каждый город ровно один раз и возвращается в исходный город?
По мере того, как число городов или(n)увеличивается, сложность увеличивается… абсурдно.
В 10 городах возможные части для рассмотрения уже находятся на уровне 362 880, что приведет к остановке вашей кодовой базы, поскольку ваш процессор будет навсегда закреплен на 100%, решая эту проблему.
Для сравнения
10 городов имеют 362 880 вариаций
если к остановке продавцов добавить еще 6 городов, то получится 1 307 674 368 000 вариантов.
Теперь сложность увеличилась в 3,6 миллиона раз.
Таким образом, разработчики должны поддерживать эффективность своего кода и простоту его выполнения. Обозначение Big O может быть полезным способом сделать это.
Спасибо, что прочитали это, я надеюсь, что это помогло вам понять основы нотации Big O.
Ресурсы:
