Если вы не сталкивались с большой буквы во время своего программирования, вы обязательно столкнетесь с ней в какой-то момент. Когда я впервые наткнулся на это, я был совершенно ошарашен! Тем не менее, если больше углубиться в это и работать с примерами, это был важный момент для лица. В этом блоге я буду обсуждать нотацию Big O и рассматривать несколько основных аспектов, которые помогут вам глубже погрузиться в ее более сложные области.

Почему большой и почему О? 🤔

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

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

Шаг за шагом 🪜

Big O стремится сосредоточить внимание на количестве шагов по отношению к количеству заданных элементов. Таким образом, логика заключает, что если количество предпринятых шагов намного меньше, чем количество элементов, которые рассматриваются в этом алгоритме, это был бы эффективный алгоритм. Однако противоположный сценарий также дает противоположный результат, и также будет средняя точка, где количество шагов совпадает с количеством элементов. Наконец, вы можете / столкнетесь со сценарием, в котором, независимо от количества элементов, алгоритм всегда будет выполнять одно и то же количество шагов.

Большой O из N - O из N - O (n) 📏

Помните, что лучший способ описать Big O - это количество шагов, предпринятых для выполнения алгоритма, по отношению к количеству предоставленных элементов. Или, другими словами, если имеется N элементов, сколько шагов сделает алгоритм?

Во-первых, мы будем смотреть на O (n) (произносится как любой заголовок выше). O (n) сообщает нам, что алгоритм будет выполнен за то же количество шагов, что и элементов. Итак, если есть 10 элементов, для завершения алгоритма потребуется 10 шагов. Если есть 20 элементов, потребуется 20 шагов. Если есть 30 элементов, потребуется 30 шагов. Вы уловили картину.

Говоря об изображениях, давайте посмотрим на это с помощью графика:

Ось y (время выполнения) относится к количеству шагов, а ось x (объем данных) относится к количеству элементов. Как видите, количество шагов растет прямо пропорционально размеру обрабатываемых элементов и поэтому известно как линейный алгоритм.

Вот пример функции JavaScript, которая показывает O (n):

function arrSum(array) {
  let sum = 0;
  
  for (let i = 0; i < array; i++) {
    sum += array[i];
  }
  
  return sum;
}

Большой O из 1 - O из 1 - O (1) ☝🏽

Теперь мы будем смотреть на O (1) (произносится как любой заголовок выше). O (1) сообщает нам, что алгоритм будет завершен за одно и то же количество шагов независимо от количества элементов. Итак, если есть 10 элементов, для завершения алгоритма потребуется 5 шагов. Если есть 20 элементов, также потребуется 5 шагов. Если есть 30 элементов, снова потребуется 5 шагов. Таким образом, «1» относится к постоянному количеству шагов, не обязательно «1» шаг.

Изобразим это на графике:

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

Вот пример функции JavaScript, которая показывает O (1):

function isLeapYear(year) {
  return (year % 100 === 0) ? (year % 400 === 0) : (year % 4 === 0);
}

Независимо от того, какой год введен, 1990 или 2021, алгоритм не будет различаться по количеству шагов и, следовательно, будет O (1).

Большая O из N в квадрате - O из N в квадрате - O (n²) 🔲

Здесь мы будем смотреть на O (n²) (произносится как любой из заголовков выше). O (n²) говорит нам, что алгоритм будет завершен в квадрате количества шагов по отношению к элементам. Итак, если есть 10 элементов, для завершения алгоритма потребуется 100 шагов. Если есть 20 элементов, потребуется 400 шагов. Если есть 30 элементов, потребуется 900 шагов. Эта запись показывает нам экспоненциальный рост шагов и крайне неэффективна.

Посмотрим, как это будет представлено на графике:

O (n²) представляет производительность, которая прямо пропорциональна квадрату размера элементов. По мере увеличения элементов на 1 будет быстрый рост ступеней.

Обычно не всегда вложенные циклы составляют O (n²). Вот пример вложенного цикла JavaScript, который может иметь значение O (n²):

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      // Your code
    }
}

Большой O журнала N - O журнала N - O (журнал n) 🪵

Наконец, мы посмотрим на O (log n) (произносится как любой из заголовков выше). Возможно, вы слышали о логарифмах, и O (log n) относится именно к этому. Логарифм представлен как log2 n, но в информатике мы опускаем 2, делая его просто O (log n). Итак, O (log n) означает, что для количества N элементов в алгоритме потребуется log2 n шагов. Если бы в алгоритме было 8 элементов, для его выполнения потребовалось бы три шага, поскольку log2 8 = 3 или, другими словами, вам нужно было бы разделить 8 на 2, 3 раза, чтобы получить 1 (8/2/2 / 2 = 1). Это эффективный алгоритм, поскольку количество шагов намного меньше количества элементов.

Посмотрим на график:

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

Вот пример функции JavaScript, которая показывает O (log n):

function chessBoardSpace(numberOfGrains) {
  let chessBoardSpaces = 1;
  let placedGrains = 1;
  while (placedGrains < numberOfGrains) {
    placedGrains *=2;
    chessBoardSpaces +=1;
  }
  return chessBoardsSpaces;
}

Эта функция вычисляет, в какой квадрат на шахматной доске вам нужно будет разместить определенное количество зерен. Например, когда вы вводите 16 в качестве numberOfGrains, это вернет 5, как если бы вы поместили 16 зерен на 5-й квадрат. Как видите, для каждого следующего квадрата количество зерен удваивается, поэтому количество шагов, предпринимаемых для завершения алгоритма, намного меньше, чем количество элементов.

Надеюсь, вы смогли узнать о различных аспектах нотации Big O и о том, как наши алгоритмы играют огромную роль в эффективности. Пусть ваше путешествие с Big O будет стабильным!