В блоге мы узнаем о временной сложности алгоритмов и о том, почему важно знать временную сложность алгоритма.

Что такое временная сложность?

Есть несколько способов решить проблему, но какой из них выбрать? Решение, которое является наиболее эффективным и быстрым, конечно. Временная сложность алгоритма определяет количество времени, которое требуется алгоритму для выполнения, в зависимости от длины входных данных. Обратите внимание, что время выполнения зависит от длины входных данных, а не от фактического времени выполнения машины, на которой выполняется алгоритм. Фактическое время выполнения будет варьироваться на каждом компьютере в зависимости от его процессора.

Как представить временную сложность?

Мы используем сокращенную математическую запись для описания эффективности алгоритма, которая называется Большая нотация О. Буква О используется потому, что скорость роста функции также называется ее порядком. Это помогает нам понять, как время выполнения увеличивается по мере увеличения размера ввода.

Типы сложностей в нотации Big O:

  • O(1):Время выполнения не зависит от размера входных данных задачи.
  • O(n): задача требует небольшого количества времени обработки для каждого элемента во входных данных. Это случай линейной сложности, когда у нас есть один цикл из n итераций. Точно так же, когда у нас есть два отдельных цикла в программе, временная сложность может быть равна O(m+n).
  • O(n²):Задача обрабатывает все пары элементов. Это называется квадратичной сложностью. Это происходит, когда мы используем вложенный цикл n x n итераций.
  • O(log n): когда большая проблема решается путем преобразования ее в меньшую на некоторую постоянную долю. Это называется логарифмической сложностью и возникает при двоичном поиске.
  • O(n log n): когда проблема разбивается на более мелкие подзадачи, решается их независимо и комбинируются решения. Это называется линейной арифмической сложностью. Это происходит при сортировке слиянием.
  • O(n!): медленно увеличивается для меньших входных данных, но после точки увеличивается экспоненциально.

Как измерить время, затрачиваемое алгоритмом в javascript?

Мы используем функции console.time() и console.timeEnd(), помещая console.time() в то место в коде, где мы хотим начать запись времени, и помещая функцию timeEnd в то время, когда вы хотите остановить запись. время.

let a = [1,2,3,4,5,6,7,8,9]

console.time();
for(let i=0;i<a.length;i++){
    for(let j=0;j<a.length;j++){
        console.log(a[i],a[j])
    }
}

console.timeEnd();  // prints 9.111 ms

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

Зачем нам, веб-разработчикам, изучать временную сложность?

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

Спасибо за чтение. В моем следующем блоге мы начнем изучать асинхронный javascript.