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

Подумайте о том, чтобы пойти на вечеринку, парад или концерт в парке. Если я хочу знать, насколько крупным было мероприятие, я ищу не точное количество 457 участников или 3278 человек, а скорее порядок величины - было ли оно выражено однозначными числами, десятками (от 10 до 99), сотнями (100–999), тысячами, десятками тысяч и т. д. Другой способ записать все это — сказать, что событие было в порядке 1, 10, 100, 1000, 10000 и т. д.

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

O(N) ~ линейный

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

Величина O(N) означает, что по мере увеличения N (размера списка) увеличивается и время, необходимое для вычисления N проверок. Итак, если размер списка N равен 1, алгоритму потребуется 1 единица времени, чтобы найти ответ. Если N=2, время = 2 и т. д. Он растет с постоянной скоростью один к одному (если вы увеличите N на 1, время увеличится на 1).

O(1) – константа

Предположим, теперь у нас есть число N любого размера, и мы хотим знать, четное оно или нечетное. Затем все, что нам нужно сделать, это разделить N на два и проверить, равен ли остаток 0 или 1. Таким образом, требуется всего одна проверка, чтобы определить, является ли число четным или нечетным, и это независимо от размер N. То есть не имеет значения, насколько велико N, оно может быть маленьким, или вы можете увеличить его до любого желаемого размера, и всегда потребуется всего одна проверка, чтобы определить, четное оно или нечетное. . Принадлежность к O(1) означает, что ваши вычисления всегда будут занимать 1 единицу времени, независимо от размера N (в отличие от нашего предыдущего примера, где, когда вы делаете N больше, то и время тоже увеличивается).

O(N²) ~ квадратичный

Предположим, мы хотим умножить два числа из N цифр каждое. Например, предположим, что у нас есть число 47238 и число 99361, оба с N=5 цифрами. Чтобы умножить их, нам нужно умножить каждую цифру из первого числа на каждую цифру из второго. Например, для 47238 (что равно 40000 + 7000 + 2000 + 30 + 8) у нас будет: 8*1 + 30*1 + 200*1 + 7000*1 + 40000*1, где 1 происходит от 99361. Затем нам придется проделать тот же процесс для 6, 3, 9 и 9. Другими словами, нам потребуется то, что мы только что вычислили, но всего 5 раз, и вы видите, что наша сумма содержит 5 членов, поэтому мы нужно 5*5 = 25 вычислений, что равно N*N или N². Таким образом, порядок O(N²) означает, что каким бы ни было N, время, необходимое для вычислений, будет равно квадрату этого N. .

O(2^N) ~ экспоненциальная

Хорошо, шаг за шагом. Экспоненциальные функции — это функции, в которых переменная (то, что становится больше) является фактическим показателем степени, а не основанием, как указано выше. Теперь основание равно 2 (или другое постоянное число), но показатель степени меняется. Так как N растет на 1, 2, 3, 4, …, время увеличивается на 2¹, 2², 2³, 2⁴, …

Что за пример? В порядке. Числа Фибоначчи — это числа 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … вы получаете следующее, складывая два предыдущих. Легко, верно? Предположим, вы хотите вычислить n-е число Фибоначчи Fn. Вам потребуется:

Fn

= Fn-1 + Fn-2

= Fn-2 + Fn-3 + Fn-3 + Fn-4

= так далее и тому подобное

Первая строка дает вам 2 вычисления, вторая строка дает вам 4 вычисления, 3-я строка — 8, 4-я — 16 и так далее. Вы видите, что в каждой последующей строке это 2, затем 2*2, затем 2*2*2, затем 2*2*2*2 и т. д., так что в самой последней строке у нас будет 2*2*2*… *2 n раз, или 2^n. Программе потребуется произвести столько вычислений, чтобы найти значение Fn.

O(log n) ~ логарифмический

Последний. Есть и другие «ковши» порядка, но это более распространенные, с которых стоит начать знакомство. Предположим, у нас есть большой список чисел (например, 1, 3, 7, 34, 56, 235, 4567 и т. д.), но на этот раз он упорядочен (скажем, по возрастанию), и мы ищем конкретный элемент. Мы могли бы проверять каждый элемент один за другим, как мы делали в первом примере, но другим лучшим подходом было бы разделить этот список на две корзины, прямо посередине, и если искомое число больше, чем первая корзина, тогда мы знаем, что нужно игнорировать первое ведро и сосредоточиться на втором ведре. Мы повторяем этот процесс деления пополам со вторым ведром, разделив его на две части и проделав ту же проверку. Поскольку у нас есть наихудший сценарий, наше число будет отображаться только до самого последнего деления пополам, когда мы получим только одно число в корзине.

Итак, сколько раз нам нужно проверить наполовину? Допустим, в нашем списке 64 элемента. Наша первая проверка создаст ведра размером 32, затем 16, 8, 4, 2 и, наконец, 1. Итак, это 6 полупроверок. Для списка из 64 элементов потребовалось 6 единиц времени. Какая операция дала вам это? Итак, если вы возведете 2 в степень 6, вы получите 64, и это то, что представляет собой log(base2)64, это означает «в какой показатель степени мы возводим 2, чтобы получить 64». ? Это 6.

Надеюсь это поможет. Стоит изобразить некоторые из них в виде графика, чтобы увидеть их поведение по мере того, как N становится очень большим. Предлагаю воспользоваться калькулятором Desmos.