/ ↲
    Расширенный поиск

    Веб-платформа

    Как анализировать алгоритмы?

    Разбираемся, что такое сложность алгоритмов, как посчитать сложность по времени и по памяти.

    Время чтения: 8 мин

    Кратко

    Скопировано

    Вычислительная сложность алгоритма описывает, как выполняемый алгоритмом объём работы зависит от размера входных данных.

    Обычно у алгоритмов бывает две сложности:

    • временная сложность — как количество операций, которые выполняются при работе алгоритма, связано с объёмом входных данных;
    • сложность по памяти — как количество памяти, которое нужно алгоритму, связано с размером входных данных.

    В обоих случаях оцениваем, как связаны используемые алгоритмом ресурсы (время или память) с количеством входных данных. Может показаться, что алгоритм медленнее работает и потребляет больше памяти, когда размер входных данных большой. Это не всегда так. К примеру, скорее всего время работы функции const doNothing = (...asManyDataAsYouLike) => { } не будет зависеть от количества переданных ей аргументов. Оценка сложности этой функции — O(1). Попробуем разобраться, что это значит.

    Способы оценки сложности (обозначения)

    Скопировано

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

    Теперь разберём некоторые способы оценки сложности алгоритма.

    O (О-большое)

    Скопировано

    O, читается как «О», «О-большое» или «биг (big) О», описывает оценку сложности сверху. То есть максимальное количество операций, которое алгоритм может выполнить в худшем случае. В скобках после О указывают функцию, которая ограничивает сложность. Например, O(n) означает, что сложность алгоритма растёт линейно. Это означает, что время выполнения алгоритма увеличивается прямо пропорционально размеру входных данных (к примеру, есть список из 10 элементов, алгоритм займёт определённое время. Но если будет 20 элементов, то алгоритм займёт в два раза больше времени). При этом как именно линейно не важно. Давайте рассмотрим несколько примеров.

    Вычислительная сложность этого алгоритма — O(n). Мы обрабатываем каждый элемент один раз. Если в нашем массиве n элементов, мы выполним тело функции reduce n раз.

            
          
            const sum = (someArray) => someArray.reduce((sum, value) => sum + value, 0)
            const sum = (someArray) => someArray.reduce((sum, value) => sum + value, 0)

    Вычислительная сложность этого алгоритма тоже будет O(n). Мы обрабатываем каждый элемент два раза. Если в нашем массиве n элементов, то выполним тело функции reduce 2 × n раз. n раз для суммирования и n раз для произведения. Это описывает формула O(k × n) = O(n). В нашем случае коэффициент не имеет значения, так как он не зависит от размера входных данных.

            
          
          const sumAndProd = (someArray) => {  const sum = (someArray) => someArray.reduce((sum, value) => sum + value, 0)  const prod = (someArray) => someArray.reduce((prod, value) => prod * value, 1)  return sum * prod}
          const sumAndProd = (someArray) => {
  const sum = (someArray) => someArray.reduce((sum, value) => sum + value, 0)
  const prod = (someArray) => someArray.reduce((prod, value) => prod * value, 1)
  return sum * prod
}

    Ω (сигма)

    Скопировано

    Ω, читается как «Сигма» или «Сигма-большая», описывает оценку сложности снизу. То есть минимальное количество операций, которое алгоритм будет выполнять в лучшем случае. В скобках после Ω указывают функцию, которая ограничивает сложность. Например Ω(n) означает, что сложность растёт так же или быстрее, чем линейно. Например, квадратичная сложность n × n — это тоже Ω(n).

    Θ (тета)

    Скопировано

    Θ, читается как «Тета» или «Тета-большая», описывает плотную оценку алгоритма. В скобках после ϴ указывают функцию, которая ограничивает сложность как сверху, так и снизу. Рассмотрим предыдущий пример:

            
          
          const sumAndProd = (someArray) => {  const sum = (someArray) => someArray.reduce((sum, value) => sum + value, 0)  const prod = (someArray) => someArray.reduce((prod, value) => prod * value, 1)  return sum * prod}
          const sumAndProd = (someArray) => {
  const sum = (someArray) => someArray.reduce((sum, value) => sum + value, 0)
  const prod = (someArray) => someArray.reduce((prod, value) => prod * value, 1)
  return sum * prod
}

    Алгоритм выполняет 2 × n операций — n сложений и n умножений. Это значит, что количество операция сверху ограничено функцией от n или 2 × n < 3 × n, а снизу — функцией от n или 2 × n > n.

    Для полноты картины приведём точные формулировки для каждого из определений.

    • O — f(n) = O(g(n)). Есть положительное число c, которое, начиная с n, всегда выполняет условие 0 <= f(n) < c × g(n).
    • Сигма — f(n) = Ω(g(n)). Есть положительное число c , которое, начиная с n, всегда выполняет условие 0 <= f(n) <= c × g(n).
    • Тета — f(n) = ϴ(g(n)). Есть два положительных числа c1 и c2, которые, начиная с n, всегда выполняют условие c1 × g(n) <= f(n) <= c2 × n.

    Также есть алгоритмы, у которых вычислительная сложность по памяти — O(1). Их называют алгоритмами на месте (in-place). Они могут использовать дополнительную память, но её размер не зависит от количества входных данных. Например, чтобы посчитать сумму всех чисел, используем переменную с их суммой. Эта переменная занимает место, но не зависит количества складываемых чисел.

    Примеры

    Скопировано

    Ещё несколько примеров. Представим, что нужно сменить логотип, и мы выбираем дизайнера с самым большим опытом. У нас есть массив с числами, которые означают опыт в годах. Нам нужно найти максимальное число:

            
          
          function findMax(arr) {  let max = arr[0]  for (let i = 1; i < arr.length; i++) {    if (arr[i] > max) {      max = arr[i]    }  }  return max}
          function findMax(arr) {
  let max = arr[0]
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i]
    }
  }
  return max
}

    Это решение имеет временную сложность O(n). Тело цикла for выполняется для каждого элемента массива, кроме первого. Например, переменная max для массива из трёх элементов обновится два раза.

    Теперь представим, что у нас есть массив с опытом дизайнеров, который отсортирован по возрастанию. Мы всё так же хотим найти самого опытного из них:

            
          
          function findMax(arr) {  return arr[arr.length - 1]}
          function findMax(arr) {
  return arr[arr.length - 1]
}

    Этот код имеет временную сложность ϴ(1), потому что он выполняет только одну операцию, независимо от размера массива.

    Наконец, представим, что у нас есть массив чисел, которые также обозначают опыт дизайнеров, и мы сортируем числа по возрастанию от меньшего к большему:

            
          
          function sortArray(arr) {  for (let i = 0; i < arr.length; i++) {    for (let j = i + 1; j < arr.length; j++) {      if (arr[i] > arr[j]) {        let temp = arr[i]        arr[i] = arr[j]        arr[j] = temp      }    }  }  return arr}
          function sortArray(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) {
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
      }
    }
  }
  return arr
}

    Временная сложность этого кода — ϴ(n ^ 2). Он выполняет n операций для каждого элемента массива — n × n. Если массив состоит из десяти элементов, то код выполнится за 100 операций.

    Такие алгоритмы не стоит использовать для сортировки реальных массивов. Есть более эффективные сортировки с вычислительной сложностью n × log(n). Это минимально возможная вычислительная сложность для сортировки на основе сравнения двух элементов массива.

    Теперь рассмотрим пример с алгоритмом на месте. Представим, что у нас есть две корзины с яблоками, и мы хотим поменять их местами:

            
          
          let basket1 = ["яблоко", "яблоко", "яблоко"]let basket2 = ["апельсин", "апельсин", "апельсин"][basket1[0], basket2[0]] = [basket2[0], basket1[0]]console.log(basket1) // ["апельсин", "яблоко", "яблоко"]console.log(basket2) // ["яблоко", "апельсин", "апельсин"]
          let basket1 = ["яблоко", "яблоко", "яблоко"]
let basket2 = ["апельсин", "апельсин", "апельсин"]

[basket1[0], basket2[0]] = [basket2[0], basket1[0]]

console.log(basket1) // ["апельсин", "яблоко", "яблоко"]
console.log(basket2) // ["яблоко", "апельсин", "апельсин"]

    В примере меняем местами первые элементы двух массивов basket1 и basket2. Используем деструктуризацию массива для временного хранения значений элементов и меняем их местами сразу в памяти.

    На собеседовании

    Скопировано
    Задать вопрос в рубрику
    🤚 Я знаю ответ

    Viktar Nezhbart  отвечает

    Скопировано

    Основной сложностью данной задачи является определение уникальности элементов коллекции.

    Попробуем для начала упростить задачу. Допустим, элементами коллекции являются примитивные значения, а сама коллекция - это массив. В этом случае наше решение может быть таким:

            
          
          function getUnique (array) {  // Если это не массив, возвращаем пустой массив  if (Array.isArray(array) === false) {    return []  }  const uniqueArray = []  array.forEach(item => {    if (uniqueArray.includes(item)) {      return    }    uniqueArray.push(item)  })  return uniqueArray}
          function getUnique (array) {
  // Если это не массив, возвращаем пустой массив
  if (Array.isArray(array) === false) {
    return []
  }

  const uniqueArray = []

  array.forEach(item => {
    if (uniqueArray.includes(item)) {
      return
    }
    uniqueArray.push(item)
  })

  return uniqueArray
}

    Сначала проверяем, что аргументом функции является массив, а затем перебираем коллекцию и накапливаем в новом массиве uniqueArray только уникальные элементы. Для проверки уникальности используем метод массивов .includes().

    Проверим работу нашей функции:

            
          
          const result = getUnique([1,2,2,1,3,0,2])console.log(result)// [ 1, 2, 3, 0 ]
          const result = getUnique([1,2,2,1,3,0,2])
console.log(result)
// [ 1, 2, 3, 0 ]

    Функция работает как ожидалось, но такое решение не самое оптимальное. Если оценить сложность алгоритма, то окажется что она равна O(n^2). Для каждого элемента исходного массива необходимо осуществлять поиск в создаваемом массиве уникальных элементов.

    JavaScript имеет специальный тип для создания уникальных коллекций — Set. С его помощью решение будет намного проще:

            
          
          function getUnique (array) {  // Если это не массив, возвращаем пустой массив  if (Array.isArray(array) === false) {      return []  }  return [ ...new Set(array) ]}
          function getUnique (array) {
  // Если это не массив, возвращаем пустой массив
  if (Array.isArray(array) === false) {
      return []
  }

  return [ ...new Set(array) ]
}

    Это решение не требует перебора коллекции вручную (это произойдёт "под капотом"), так как при создании объекта Set в него попадут только уникальные элементы переданого массива. Затем, используя деструктуризацию, мы преобразуем Set обратно в массив.
    По сравнению с предыдущим вариантом, это улучшает производительность, так как поиск в коллекции Set гарантировано выполняется быстрее чем при использовании .includes().

    А как быть с объектами в качестве элементов коллекции? С точки зрения JavaScript следующие элементы являются уникальными:

            
          
          console.log(new Set([{},{},{},{}]))// Set(4) { {}, {}, {}, {} }
          console.log(new Set([{},{},{},{}]))
// Set(4) { {}, {}, {}, {} }

    Если определяете «равенство» объектов, можно воспользоваться библиотекой Lodash. В библиотеку входит метод .isEqual(), позволяющий сравнивать объекты:

            
          
          function getUnique (array) {  // Если это не массив, возвращаем пустой массив  if (Array.isArray(array) === false) {    return []  }  const uniqueArray = []  array.forEach(item => {    if (uniqueArray.some(uniqueItem => _.isEqual(item, uniqueItem))) {      return    }    uniqueArray.push(item)  })  return uniqueArray}
          function getUnique (array) {
  // Если это не массив, возвращаем пустой массив
  if (Array.isArray(array) === false) {
    return []
  }

  const uniqueArray = []

  array.forEach(item => {
    if (uniqueArray.some(uniqueItem => _.isEqual(item, uniqueItem))) {
      return
    }
    uniqueArray.push(item)
  })

  return uniqueArray
}

    Теперь перебираем элементы коллекции и накапливаем уникальные элементы в новом массиве uniqueArray, используя для поиска повторений метод массивов .some() и метод библиотеки Lodash .isEqual(). Сложность этого алгоритма равна O(n^2), так как требуется внутренний цикл для тестирования уникальности каждого элемента.

    Можно улучшить гибкость нашего решения:

    • адаптировать для использования не только массивов, но и других коллекций;
    • устранить зависимость от библиотеки Lodash и дать возможность использовать собственную функцию для проверки уникальности элемента;
    • снизить сложность алгоритма до O(n).

    Для этого проверим что аргументом функции является итерируемый объект, а обход будем осуществлять с использованием for..of. Коллекцию уникальных элементов будем накапливать используя Map. Это позволит сохранять ключи значений для ускорения определения уникальности значений. Кроме этого, добавим возможность передавать в качестве второго аргумента функцию-компаратор. Функция должна вернуть пару ключ/значение, которые будут добавлены в коллекцию уникальных элементов.
    Если функция не передана, вычисляем ключ, приводя значение к строке.

            
          
          function getUnique (collection, comparator) {  // Если это не итерируемая коллекция, возвращаем пустой массив  if (collection === null || typeof collection[Symbol.iterator] !== 'function') {    return []  }  const unique = new Map()  // Функция для получения пары ключ/значение  const getKeyAndValue = typeof comparator === 'function'    ? comparator    : (item) => {      const key = `${item}`      return [key, item]    }  for (const item of collection) {    const [key, value] = getKeyAndValue(item, unique)    unique.set(key, value)  }  return Array.from(unique.values())}
          function getUnique (collection, comparator) {
  // Если это не итерируемая коллекция, возвращаем пустой массив
  if (collection === null || typeof collection[Symbol.iterator] !== 'function') {
    return []
  }

  const unique = new Map()
  // Функция для получения пары ключ/значение
  const getKeyAndValue = typeof comparator === 'function'
    ? comparator
    : (item) => {
      const key = `${item}`
      return [key, item]
    }

  for (const item of collection) {
    const [key, value] = getKeyAndValue(item, unique)
    unique.set(key, value)
  }

  return Array.from(unique.values())
}

    Протестируем это решение без передачи компаратора:

            
          
          console.log(  getUnique([1, null, {}, [], {}, null]))// [ 1, null, {}, [] ]
          console.log(
  getUnique([1, null, {}, [], {}, null])
)

// [ 1, null, {}, [] ]

    Функция-компаратор пригодится для кастомизации логики, например если перед нами стоит задача объединить объекты на основе значения поля id:

            
          
          console.log(  getUnique(    [      { id: 2, type: 'd' },      { id: 3, category: null },      { name: 'Q', value: 42, id: 2 },      { width: 1024, size: 'big', id: 0 }    ],    (item, obj) => {      const key = item.id      const value = {        ...obj.get(key),        ...item      }      return [key, value]    }  ))// [//   { id: 2, type: 'd', name: 'Q', value: 42 },//   { id: 3, category: null },//   { width: 1024, size: 'big', id: 0 }// ]
          console.log(
  getUnique(
    [
      { id: 2, type: 'd' },
      { id: 3, category: null },
      { name: 'Q', value: 42, id: 2 },
      { width: 1024, size: 'big', id: 0 }
    ],
    (item, obj) => {
      const key = item.id
      const value = {
        ...obj.get(key),
        ...item
      }
      return [key, value]
    }
  )
)

// [
//   { id: 2, type: 'd', name: 'Q', value: 42 },
//   { id: 3, category: null },
//   { width: 1024, size: 'big', id: 0 }
// ]

    Читайте также

    • Как устроена память

      Разбираем как устроена память на примере простой модели. Знакомимся с понятиями «стек» и «куча».

    • Массив

      Ни один язык программирования не обходится без хранения списков значений. JavaScript не исключение.

    • for

      Классический цикл максимально удобен для работы со счётчиками.