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

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

function findElement(array){
  return array[0]
}

2. Логарифмическое время или O(log(n)) — время прямо пропорционально размеру входных данных. Это часто встречается в бинарных деревьях. В приведенном ниже примере будет время O(log(2)) , потому что мы умножаем i на 2. Это отличается от линейного времени из-за того, как увеличивается i.

function printString(){
   for(let i = 1; i <= 10; i *=2){
      console.log('hi')
   }
}

3. Линейное O(n). Примером линейного времени может быть итерация по массиву. Обратите внимание, что это все еще O(n) время, если вас попросят повторить только половину. Кроме того, если есть два разных массива и вам нужно перебирать их по отдельности, но в рамках одной и той же функции, это все равно считается линейным временем.

function findTwos(array){
   let result = []
   for(let element of array){
      if(element === 2){
         result.push(element)
      }
   }
   return result.length
}

4. Квазилинейный O(log(n)*n) — как и следовало ожидать, это комбинация линейного и логарифмического времени. В этом примере первый цикл представляет собой линейное время, а второй цикл — логарифмическое время.

function printString(){
   for(let i = 0; i < 3; i++){
      for(let j = 1; j < 3; j = j * 2){
         console.log("hej")
      }
   }
}

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

function pyramid(n) {
  const midpoint = Math.floor((2*n-1) / 2)
  for (let row = 0; row < n; row++){
    let level = ''
      for (let column = 0; column < 2*n-1; column++){
        if (midpoint - row <= column && midpoint + row >= column) {
          level += '#'
        } else {
          level +=' '
        }
      }
    console.log(level)
  }
}

6. Экспоненциальный или O(2n) — если вы добавите дополнительный элемент, время обработки удвоится. Это не хорошо! Если вы когда-нибудь обнаружите, что используете экспоненциальное время, попробуйте найти решение, которое имеет лучшее время.

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