Понимание временной сложности алгоритмов поможет нам оценить, будет ли масштабироваться наш код. При реализации алгоритмов также полезно понимать разницу в производительности выполнения, чтобы выбрать лучший алгоритм для вашей задачи и достичь оптимальной эффективности.
Важно отметить, что временная сложность — это не количество измеримого времени (например, x секунд), которое требуется для выполнения алгоритма; скорее это связано с количеством выполняемых операций. На количество операций, выполняемых программой, влияет размер ввода (обозначаемый как n) и способ расположения их элементов. Чтобы классифицировать алгоритмы по наихудшему сценарию, мы используем нотацию Big O, которая является функцией размера входных данных n (например, O(n) или O(n³)). Для визуализации концепции ниже приведены шпаргалка, примеры и диаграмма Big O:
1. O(1): постоянное время
O(1) включает алгоритмы, выполнение которых занимает одинаковое количество времени независимо от размера входных данных (n); эти алгоритмы имеют постоянную скорость роста. Примеры алгоритмов времени выполнения O(1):
// 1. Checking if a number is even or odd
В этом примере не имеет значения, равно ли n 1 или 1000, блок кода будет выполнен только один раз.
// 2. Printing the first element from a list
// 3. Checking if an item in an array is null
// 3. Finding a value on a hash map (which is generally done in O(1) time - in unique/difficult cases O(n) time)
Примечание. Важно понимать, как реализуются операции (особенно методы массивов и объектов), чтобы определить время их выполнения. Например, хотя приведенный ниже блок кода запускается только один раз для каждого элемента, на самом деле он запускается несколько раз для каждого элемента в массиве.
Кроме того, хотите верьте, хотите нет, примитивные математические операции (например, +, *, -, / и %) имеют постоянное время выполнения, поскольку большинство языков программирования ограничивают числа максимальным значением (в JavaScript это число.MAX_VALUE равно 1,7976). …). Следовательно, вы не можете оперировать числами, которые дают большее значение, чем MAX_VALUE, и эти примитивные математические операции должны выполняться за фиксированное количество инструкций (O(1)).
2. O(n): линейное время
Алгоритмы, работающие за линейное время, очень распространены; в этой среде выполнения подразумевается, что каждый элемент из ввода посещается в наихудшем сценарии. Линейное время означает, что по мере роста ввода пропорционально увеличивается время выполнения. Как следует из названия, на этот раз сложность имеет линейную скорость роста. Примеры алгоритмов времени выполнения O (n) включают:
// 1. Finding the maximum and minimum values in an array
Функция getMaxValue() проверит каждый элемент массива. Счетчик был добавлен, чтобы явно показать, сколько раз функция выполнила блок кода. В этом примере n == 4 (в массиве 4 элемента) и счетчик == 4, а также сразу после завершения выполнения.
// 2. Finding a given element in a collection
// 3. Printing all the values in a list
3. O(n²) — квадратичное время
Алгоритм с квадратичной временной сложностью имеет скорость роста n². Например, если вход (n) == 2, он выполнит 4 операции. Примеры алгоритмов времени выполнения O (n²) включают:
// 1. Checking if a collection has any duplicate values
// 2. Sorting items in a collection using bubble sort, insertion sort, or selection sort
// 3. Finding all pairs in a collection
4. O(n^c) — Полиномиальное время
В полиномиальном режиме выполнения c > 1. O(n²) преобразуется в два вложенных цикла; три вложенных цикла + считаются полиномиальными (кубическими, квадратичными и т.д.). Полиномиальные среды выполнения занимают много времени для вычислений, поскольку входные данные быстро растут, и поэтому их обычно избегают. Пример алгоритмов времени выполнения O (n ^ c) включает:
// 1. Finding the solution to a multi-variable equation (via triple nested loops)
