Важной концепцией в информатике, когда вы пытаетесь понять алгоритмы, является нотация большого O. Нотация Big O описывает, сколько времени требуется программе для выполнения в связи с изменением размера ввода.

Большой O был создан немецкими математиками Паулем Бахманном и Эдмундом Ландау и представляет собой тип асимптотической записи для наихудшего времени выполнения алгоритма. Размышляя о времени выполнения программы, мы можем разделить его на три категории: наилучшее, наихудшее и среднее. Мы в основном заинтересованы в определении наихудшего или среднего случая, чтобы дать нам хорошую основу для вычислительной скорости нашей программы. Вот как пригодится понимание большого О.

Есть несколько больших нотаций O, которые ученые-компьютерщики используют для описания наихудшего времени выполнения программы. Для краткости мы обсудим здесь лишь некоторые из них.

И. Постоянная временная сложность

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

Из этого графика видно, что по мере увеличения размера ввода время выполнения остается прежним. Вот пример алгоритма с постоянным временем в коде:

function evenOrOdd(number) {
   if (number % 2 === 0) {
     return "even";
   } else {
     return "odd";
   }
}

Чтобы определить временную сложность этого алгоритма, мы должны посмотреть, сколько раз выполняется каждое выражение. Вот еще раз алгоритм:

function evenOrOdd(number) {
  if (number % 2 === 0) {  // executed once
     return "even";  // executed once
  } else {    // executed once
     return "odd";  // executed once 
  }
}
evenOrOdd(4) // => even
evenOrOdd(7) // => odd

В этом примере мы видим, что независимо от того, какое число мы вводим в качестве аргумента, выражения все равно выполняются только один раз. Поскольку выражения выполняются только один раз, мы можем определить, что временная сложность этого алгоритма равна O(1) или постоянной временной сложности.

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

II. Линейная временная сложность

Еще одна важная нотация O, о которой стоит упомянуть, — это O(n), также известная как линейная временная сложность. Мы уже обсуждали значение O, но n определяет размер входных данных алгоритма. Ниже мы видим пример алгоритма, работающего за время O(n). Попытайтесь понять, почему это так.

function repeatStr (n, s) {
 let string = '';
  for(let i = 0; i < n; i++) {
    string += s
  }
  return string
}

Надеюсь, вы смогли подсчитать, сколько раз выполнялось каждое выражение. Это был своего рода вопрос с подвохом, поскольку я никогда не объяснял, что происходит, когда мы не знаем, сколько раз будет выполняться выражение. Давайте еще раз посмотрим.

function repeatStr (n, s) {
 let string = '';       // executed once
  for(let i = 0; i < n; i++) {      // executed once 
    string += s       // executed n times
  }
  return string // executed once
}
repeatStr(3, "hello") // => "hellohellohello"
// 0(n)

Глядя на этот алгоритм, мы видим, что есть разница по сравнению с алгоритмом постоянного времени. В основном это введение цикла. Количество запусков цикла зависит от размера n. Поскольку время выполнения увеличивается пропорционально размеру входных данных, этот алгоритм будет выполняться за линейное время O(n).

III. Квадратичная временная сложность

Квадратичная временная сложность или O (n²) — это обычная временная сложность, при которой входные данные возводятся в квадрат. Это приводит к менее чем идеальному времени выполнения, но стоит упомянуть, поскольку это довольно распространено, особенно в некоторых алгоритмах сортировки.

function bubbleSort(array) {
 
 let isSorted = false;
let counter = 0;
while (!isSorted) { 
    isSorted = true; 
    for (let i = 0; i < array.length - 1 - counter; i++) 
      if (array[i] > array[i + 1]) { 
        swap(i, i + 1, array);  
        isSorted = false;
      }
    counter++;
  }
return array;
}
function swap(i, j, array) {
  let temp = array[j];
  array[j] = array[i];
  array[i] = temp;
}

Приведенный выше код представляет собой алгоритм сортировки, известный как пузырьковая сортировка. Мы видим, что он имеет некоторые общие характеристики ранее показанных алгоритмов, но с одним существенным изменением. Мы видим, что выполняются два цикла, и один цикл находится внутри другого. Когда мы вернемся к подсчету того, сколько раз выполняется каждое выражение, мы увидим, что в худшем случае время выполнения для выражений внутри оператора if равно n², потому что оно вложено в два цикла. Если бы оператор if находился только внутри одного цикла, временная сложность была бы всего O(n), потому что внутреннее выражение выполнялось бы n раз. Наличие вложенного цикла означает, что выражение будет выполняться O(n²) раз.

Важное замечание, однако, заключается в том, что если бы в алгоритме было больше циклов, но они не были вложенными, время выполнения алгоритма, скорее всего, было бы O(n), потому что внутренние выражения в циклах выполнялись бы только n раз. Итак, если у нас было 1n + 1n = 2n, мы опускаем коэффициент, и у нас остается только n.

Сводка

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