Обзор временной сложности и BigO

Вступление

Сложность времени и нотация BigO - два важных понятия в программировании. Я помню, как впервые услышал слово «BigO» и подумал, что это какая-то плитка шоколада или конфеты. Но нет, к сожалению, BigO не так хорош, но очень важно помнить об этих двух концепциях при программировании.

Эти концепции используются для создания более эффективного кода, который работает быстрее. Есть еще кое-что, называемое космической сложностью, что является еще одной важной концепцией, которую следует иметь в виду при программировании. Сложность пространства представляет собой объем памяти, который функция будет использовать для выполнения. Space Complexity также использует нотацию BigO, но в этом блоге я собираюсь больше поговорить о Time Complexity. Итак, без дальнейших подробностей, давайте погрузимся в это!

Сложность по времени - это способ описать время, которое потребуется функции или алгоритму для выполнения при заданном входе. BigO - это «инструмент» или визуальное представление сложности времени, нотация BigO похожа на линейку, измеряющую время.

Прежде чем мы углубимся в код, давайте посмотрим, какие существуют различные типы временной сложности. Итак, у нас есть три основных типа временной сложности: постоянное время, линейное время и квадратичное время. Есть также логарифмическое время, факторное время и экспоненциальное время, но я подробно остановлюсь на них в другом блоге, потому что они немного сложнее.

ПОСТОЯННОЕ ВРЕМЯ

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

В нотации BigO мы представляем это «O (1)», потому что независимо от того, какой ввод - это количество шагов, которые функция должна будет выполнить, то же самое, так что «O (1)». Важно отметить, что когда мы говорим о BigO, мы хотим измерить структуру алгоритма. Есть что-то, называемое «отбрасывание констант», что простыми словами означает, что если функция будет делать 2 шага для получения результата, но это количество шагов одинаково независимо от ввода, тогда функция все равно будет считаться «O». (1) », а не« O (2) », потому что мы имеем в виду поведение с BigO, а не количество. Итак, давайте посмотрим, сможем ли мы представить это с помощью кода на очень простом примере.

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

Здесь у нас есть та же функция, но мы добавили к ней еще кое-что, теперь мы хотим, чтобы наша функция называла дату, но не волнуйтесь, эта функция по-прежнему считается постоянной времени, потому что независимо от того, какой ввод является, шаги всегда будет два, но мы бы представили это как «O (1)», а не как «O (2)».

ЛИНЕЙНОЕ ВРЕМЯ

Тогда у нас есть линейное время. Линейное время представляет собой функцию, которая займет больше времени, если ввод больше, поэтому чем больше ввод, тем больше времени потребуется.

В нотации BigO мы представляем это «O (n)». Итак, что это за «n» внутри круглых скобок, «n» представляет количество процессов или входных данных, которые функция примет для выполнения задачи, но если задача занимает 100 шагов, мы бы не представляли ее как «O ( 100 (n)) », мы отбросим константы и просто скажем« O (n) ». Допустим, у нас была та же функция, что и раньше, но теперь мы хотим сказать привет всей семье!

Итак, теперь мы видим, что мы перебираем массив элементов, допустим, что Карла вышла замуж, а у Дэвида были близнецы, это еще три члена семьи, поэтому, если бы мы снова запустили эту функцию, на входе теперь будет 6 вместо 3, поэтому теперь функция должна будет сделать еще 3 итерации, так что это займет немного больше времени. Чтобы эти изменения во времени стали важными, требуется значительно больший объем данных, поэтому, если бы мы проверили и увидели разницу во времени между 3 и 6 итерациями, это, вероятно, даже не было бы больше миллисекунды, но скажем, что мы работали с именами 1000000 семей. Разница была бы гораздо более существенной.

Квадратичное время

Наконец, у нас есть квадратичное время. Квадратичное время представляет функцию, производительность которой пропорциональна квадрату заданного ввода.

То, как мы представляем это в нотации BigO, - это «O (n²)». Обратите внимание, что «n» возведено в квадрат, что означает, что теперь ввод будет обрабатываться дважды, прежде чем он представит результат, звучит как-то избыточно, верно? Так что этого типа времени следует избегать, потому что оно больше всего увеличивается в зависимости от ввода. Итак, теперь предположим, что мы хотим сделать так, чтобы наша функция заставляла каждого члена каждого члена семьи обмениваться рукопожатием со всеми другими членами семьи.

Итак, это был бы пример квадратичной функции. Мы видим, что один цикл находится внутри другого, что приводит к экспоненциальному увеличению времени. Поскольку массив «семейства» повторяется дважды, мы называем его «O (n²)», потому что входные данные проходят через 2 разных процесса в одной функции, поэтому, если массив увеличивается, итерации теперь будут занимать удвоенное время, дважды и так далее. Существует также кубическая сложность времени, которая будет такой же, но с тремя циклами, поэтому рост массива увеличится на 3.

Заключение

Итак, мы идем, краткий обзор сложности времени и нотации BigO. Об этих концепциях можно узнать больше, и я, вероятно, напишу о них в отдельном блоге, но это хороший обзор основных и наиболее практических знаний. Спасибо за чтение, и я надеюсь, что этот блог помог вам немного больше понять эти концепции, console.log («Мир!»).