Если вы веб-разработчик или программист в целом, вы, скорее всего, написали алгоритмы для различных задач. Примерами являются: поиск по таблице, сортировка массива чисел по убыванию значения, вычисление кратчайшего пути, чтобы добраться до местоположения … Но что квалифицирует алгоритм как хороший алгоритм?
Одной из спецификаций алгоритма является его корректность. Вы, вероятно, предположите, что ваш алгоритм работает после его тестирования несколько раз. Однако, если вы можете математически доказать, что ваш алгоритм будет работать, как и ожидалось, для каждого возможного входного значения, это огромный бонус. Я не буду углубляться в эту тему в этом письме.
Другая спецификация — это ее эффективность: как вычислительное время соотносится с количеством вводимых данных? Это линейное отношение? Увеличивается ли время вычислений экспоненциально для удвоения затрат? Вот о чем эта статья.
Сложность времени
Временная сложность — это, как упоминалось выше, отношение времени вычислений и количества входных данных. Обычно это размер массива или объекта. Временная сложность также бесполезна для простых функций, таких как извлечение имен пользователей из базы данных, объединение строк или шифрование паролей. Он используется больше для сортировки функций, рекурсивных вычислений и вещей, которые обычно занимают больше вычислительного времени.
Это не потому, что нам не важно время выполнения этой функции, а потому, что разница незначительна. Нам все равно, если для получения имени пользователя требуется 10 мс, а не 3 мс. Однако, если у нас есть алгоритм рекурсивной сортировки, который занимает 400 мс, и мы можем уменьшить его до 50 мс, это было бы интересно сделать.
Как вы можете догадаться, чем меньше вычислительное время, тем эффективнее алгоритм. Следующий вопрос: «Как мы можем определить сложность времени универсальным способом?». Вот где мы будем использовать «Big O обозначения».
Обозначение Big O
Обозначение Big O — это обозначение временной сложности алгоритма. Это математическое представление верхней границы предела коэффициента масштабирования алгоритма. Например, если мы удвоим размер входного массива, насколько увеличится время вычислений? Это может стать понятным с двумя примерами:
$numbers = array ( 14 , 82 , 4 , 0 , 24 , 28 ); foreach ( $numbers as $number ) { echo $number ; } Представьте, что массив $numbers является аргументом функции. У нас есть цикл foreach, проходящий через его элементы. Если мы посчитаем время, необходимое для выполнения кода, что произойдет, если мы удвоим размер массива? В этом примере мы легко видим, что он удвоит время выполнения. Мы видим, что существует линейная зависимость между размером массива и временем вычислений. Поэтому, если мы напишем размер массива как n, мы можем записать временную сложность как O (n).
Другой пример:
$numbers = array ( 14 , 82 , 4 , 0 , 24 , 28 ); foreach ( $numbers as $number1 ) { foreach ( $numbers as $number2 ) { if ( $number1 >= $number2 ) { echo $number1 . " is greater than or equal to " . $number2 ; } else { echo $number1 . " is smaller than " . $number2 ; } } }
В этом фрагменте кода есть цикл foreach, расположенный внутри другого цикла foreach. Допустим, ‘n’ — это размер $numbers в $numbers . Затем мы повторяем n раз. Это делает общее количество циклов n². Как вы можете догадаться, мы записываем сложность времени как O (n²).
Обозначение большого О выражает масштабирование вычислительного времени и использует некоторую смесь между верхней границей и пределом этого масштабирования. Например:
$numbers = array ( 14 , 82 , 4 , 0 , 24 , 28 ); foreach ( $numbers as $number1 ) { foreach ( $numbers as $number2 ) { if ( $number1 >= $number2 ) { echo $number1 . " is greater than or equal to " . $number2 ; } else { echo $number1 . " is smaller than " . $number2 ; } } } foreach ( $numbers as $number ) { echo $number ; }
Вы можете почувствовать желание записать эту временную сложность как O (n² + n). Хотя, технически, это не неправильно, это довольно бессмысленно: вы всегда определяете сложность времени как математический предел бесконечности. Если вы возьмете предел бесконечности многочлена, это всегда будет переменная с наибольшим показателем степени. Поскольку сложность времени относится к скорости изменения времени, факторы никогда не записываются перед переменными. Это означает, что, например, вы можете заменить O (5n) на O (n).
Эффективные алгоритмы
Теперь, когда мы знаем, как выразить сложность времени, мы можем взглянуть на некоторые примеры эффективных алгоритмов.
Для первого я хочу ввести другое специальное обозначение: O (log (n)), которое показывает логарифмическое отношение. Примером алгоритма, который использует это, является алгоритм двоичного поиска . Для тех, кому лень читать всю статью: вы хотите найти имя в упорядоченном по алфавиту списке и поэтому идете в центр. Если имя, которое вы ищете, предшествует этому, вы идете в центр между центральной страницей и началом (то есть 1/4). Вы продолжаете это, пока не найдете правильное имя. Временная сложность этого алгоритма составляет O (log (n)).
Если бы вы нашли имя, просматривая запись списка после записи, сложность по времени была бы O (n). Хотя это неплохо, O (log (n)) во много раз лучше. Это можно квалифицировать как эффективный алгоритм.
Неэффективные алгоритмы
Так же, как существуют эффективные алгоритмы, у нас также есть неэффективные алгоритмы. Одним из них является алгоритм Bogosort . Хотя (к счастью) никто на самом деле не использует его, он используется как демонстрация того, как вы не должны это делать. При использовании его для сортировки списка чисел в порядке убывания, он будет случайным образом выбирать порядок для списка. Затем он проверит, находится ли список в правильном порядке, если нет, он снова будет рандомизировать его. Как видите, этот алгоритм не очень эффективен и имеет временную сложность O (nxn!) (С n! Как факториал n). Если вы хотите сортировать массивы эффективным образом, ищите другой алгоритм, например Heapsort .
Написание алгоритма и его оптимизация
Сейчас я продемонстрирую, как мы можем применить сложность времени, сначала написав алгоритм, а затем напишем лучший. Вы поймете, почему последний лучше, посмотрев на его сложность. Я хочу написать функцию с массивом в качестве аргумента. Массив будет состоять из ряда натуральных чисел. Затем функция вернет новый массив, содержащий эти целые числа, отсортированные по возрастанию.
Первый алгоритм, который я буду использовать, называется сортировкой вставок. Короче говоря: он будет проходить через массив, и если целое число меньше следующего, он переключит их. Более подробное описание можно прочитать здесь .
Я реализовал алгоритм так:
function insertionSort ( $array ) { $currentNumber ; for ( $i = 1 ; $i < count ( $array ); $i ++) { $currentNumber = $array [ $i ]; while (( $i - 1 >= 0 ) && ( $currentNumber < $array [ $i - 1 ])) //While there is a smaller number to the left { $array [ $i ] = $array [ $i - 1 ]; //replace the current number by the number to its left $i --; } //there are no smaller numbers to the left anymore $array [ $i ] = $currentNumber ; //set the current number to the number that originally had index i } return $array ; } $array = array ( 4 , 29 , 9 , 2 , 9 ); print_r ( insertionSort ( $array ));
Вы видите, что есть цикл while внутри цикла for. В худшем случае сложность по времени равна O (n²). Хотя алгоритм хорошо справляется со своей задачей, O (n²) не годится, если вы работаете с массивами большего размера. Сейчас я продемонстрирую лучший алгоритм для работы: этот алгоритм сначала найдет максимум массива, который передается в качестве аргумента. Затем он создаст ассоциативный массив с именем $counting , который подсчитывает, сколько раз каждый индекс появляется в исходном массиве. Наконец, он перебирает подсчитывающий массив и добавляет каждый индекс ‘n’ раз в новый массив, где ‘n’ — это значение индекса. Например, если значение $ counting [23] равно 3, оно добавит 23 3 раза в новый массив.
function findMax ( $array ) { $maximum = $array [ 0 ]; for ( $i = 1 ; $i < count ( $array ); $i ++) { $maximum = ( $array [ $i ] > $maximum ? $array [ $i ] : $maximum ); } return $maximum ; } function increasingSort ( $array ) { $size = findMax ( $array ); $counting = array (); for ( $i = 0 ; $i <= $size ; $i ++) { $counting [ $i ] = 0 ; } for ( $i = 0 ; $i < count ( $array ); $i ++) { $counting [ $array [ $i ]]++; } $ordered = array (); for ( $i = 0 ; $i < count ( $counting ); $i ++) { for ( $j = 0 ; $j < $counting [ $i ]; $j ++) { $ordered [] = $i ; } } return $ordered ; } $array = array ( 29 , 1 , 2 , 2 , 2 , 28 , 98 ); print_r ( increasingSort ( $array ));
Временная сложность этого алгоритма O (n), намного лучше, чем алгоритм сортировки вставкой. Однако обратите внимание, что этот алгоритм может не подходить для больших чисел, которые сильно различаются, так как $array будет иметь огромный размер. Всегда убедитесь, что алгоритм соответствует ситуации.
Сложность времени — это еще не все
Теперь, когда я показал вам, какова сложность времени, обратите внимание, что вычисление времени никогда не должно быть вашим единственным фокусом. Хотя вы всегда должны пытаться выяснить, достаточно ли эффективен ваш алгоритм по времени, есть и другие аспекты, которые следует учитывать. Вычислительное время не имеет значения, если вам нужно отсортировать десять элементов, так что не тратьте время на это. Кроме того, для большинства задач, таких как сортировка, поиск записей и т. Д., Уже существуют различные эффективные и проверенные алгоритмы, которые ждут вас в Google.