Сложность алгоритмов
В прошлой статье мы рассматривали алгоритм бинарного поиска, и в процессе рассуждений об его обоснованности упоминали такую вещь, как «сложность алгоритма». Предлагаю рассмотреть ее более подробно, взяв за практический пример немного доработанную программу из предыдущей статьи.
Теория. Что такое сложность алгоритма?
Для начала надо определиться, о чем вообще идет речь. Что такое эта самая сложность алгоритма в физическом ее понимании?
Если говорить простым языком, то это время, затрачиваемое алгоритмом на достижение конечной цели. Основной целью любого алгоритма является сокращение времени решения задачи. Согласитесь, что выполнять какие-то простейшие действия с ожиданием в несколько дней (а может быть и гораздо больше, как мы убедимся далее), будет как минимум некомфортно.
Время (или сложность) алгоритмов принято обозначать большой буквой О. Это просто буква, видя которую половина программистов подумает «Опять эта непонятная фигня!», а вторая половина посмотрит более внимательно и сделает соответствующие выводы. Поначалу я относился к первой категории: когда нам рассказывали о сложности и О, я не понимал ровным счетом ничего, как и половина нашей группы (выводы сделаны на основе вопросов преподавателю и последующих обсуждений в приватных группах соцсетей). Лишь спустя довольно долгое время я решил напрячь мозги и вникнуть наконец в эту… основу основ, да, по-другому назвать это будет неправильно.
Почему вообще это важно? Представьте, что вы программируете некий алгоритм, который должен делать что-то довольно емкое в кратчайшие сроки. Например, автопилот «Теслы» должен рассчитать наимение опасную траекторию движения в случае аварийной ситуации. В процессе работы у вас постоянно должен возникать вопрос «А правильно ли я делаю? Может, можно все это ускорить?». Ведь если написать громоздкий и медленный алгоритм, может прозойти непоправимое, т.к. ваша программа просто не успеет вовремя сработать.
Возьмем для примера бинарный поиск и поиск перебором. В качестве примера рассмотрим массив на 100 элементов. При поиске в массиве перебором нужно будет произвести 100 операций, каждая из которых займет, допустим, 1 мс. То есть для поиска решения нужно будет потратить 100 мс. При бинарном поиске время работы будет в разы меньше, т.к. мы каждый раз делим на 2, а не идем подряд по всем элементам, поэтому, условно, будет не более 10 попыток. То есть поиск решения займет 10 мс против 100 мс. А теперь представим, что элементов у нас не 100, а 10 миллиардов…
Нужно понимать, что «время» здесь абстрактная величина, а не четкое количество миллисекунд на операцию, одинаковое для каждого случая работы с упомянутым алгоритмом.
Какие бывают сложности алгоритмов
Выше мы рассмотрели уже два варианта сложности алгоритма: линейная и логарифмическая. А точнее, это линейное и логарифмическое время выполнения алгоритма. Чувствую, как вы сейчас напряглись, т.к. мало кто помнит со школы, что такое логарифм. Но на самом деле здесь все довольно просто.
В первом случае мы имеем линейный рост времени работы: на 100 элементов нужно 100 мс, на 1000 — 1000 мс, на 1000000 — 1000000 мс. Такой вид сложности записывается как O(n), где n — количество шагов для достижения конечной цели, и в данном случае оно равно количеству элементов.
А что получается во втором случае? За «шаг» алгоритма можно принять момент деления на 2. Сколько раз можно поделить 100 на 2, пока не остатнется 1 (делим без остатка целые числа). Это число можно записать как логарифм от n, то есть запись будет выглядеть так — O(log n).
Логарифмом числа b по основанию a называют показатель степени с основанием a, равной b. То есть, попросту говоря, логарифм — это степень, в которую нужно возвести a для получения b. Однако у логарифма есть условия или ограничения, что основание а больше нуля и не равно единице, а также показатель b больше нуля.
То есть здесь временем работы алгоритма будет количество раз, за которое деленное на 2 исходное количество элементов массива дойдет до 1 элемента. В нашем случае это около 7 раз, то есть сложность бинарного алгоритма для массива из 100 элементов будет равна 7 против 100 у простого поиска перебором.
В реальности вариантов времени работы алгоритма несколько больше, чем две. Наиболее часто встречающимися можно назвать такие:
- O(n) — линейное время;
- O(log n) — логарифмическое время;
- O(n * log n) — линейное, помноженное на логарифмическое для каждой итерации;
- O(n2) — линейное в квадрате;
- O(n!) — факториальное, стремящееся к бесконечности.
Если заходит речь про сложность алгоритмов, то нельзя не сказать про всем известную задачу о коммиворяжере, которая не решена до сих пор несмотря на почтенный ее возраст, и олицетворяет собой последний вариант времени алгоритма.
Задача о коммивояжере
Это одна из самый старейших задач теории вычислений, уходящая корнями аж в далекий 1930 год, когде ее озвучил на очередном собрании математиков Карл Менгер. Задача была известна и ранее, и некоторые схожие описания встречаются столетием раньше, но в текущем известном нам описании она была сформирована в эти годы.
Эта задача особенна тем, что ее сложность растет с каждым шагом с бешеной скоростью, в результате чего время выполнения алгоритма по ее решению стремится к бесконечности.
Условия задачи просты: есть коммивояжер, который должен объехать пять городов. Число городов может быть разным, пять взято просто для примера. Задача: найти оптимальный маршрут его передвижения так, чтобы он проехал минимальное расстояние.
Самым простым решением приходит в голову следующее: перебрать все возможные комбинации порядке следования городов, суммировать все расстояния, а затем выбрать кратчайшее. Но… Для 5 городов потребуется выполнить 120 перестановок маршрута, а значит 120 операций. Под перестановками понимается следующее: от первого города возможны 4 направления к следующему. О каждого следующего еще по 3…
Вроде звучит неплохо. Но для 6 городов потребуется уже 720 операций. Для 7 — 5040. И так далее. Уже на 15 городах количество операций убегает далеко за миллиардное значение. Поэтому решение этой задачи имеет сложность O(n!) и называется «факториальным».
Факториа́л — функция, определённая на множестве неотрицательных целых чисел. Название происходит от лат. factorialis — действующий, производящий, умножающий; обозначается n!, произносится эн факториа́л. Факториал натурального числа n определяется как произведение всех натуральных чисел от 1 до n включительно.
Исходя из определения факториала следует, что чем больше в нем основание n, тем больше результат, причем возрастает он очень быстро.
Далее, думаю, стоит рассмотреть на практике время работы алгоритмов.
Практическая часть
Доработка программы
Чтобы рассмотреть на практике время работы алгоритма мы возьмем программу из прыдудещей статьи и внесем в нее некоторые изменения.
Для начала добавим еще одну функцию, осуществляюшую поиск по массиву простым проходом по всем его элементам:
func simpleSearch(array *[]int, lookingFor int) (int, bool) {
count := 0
start := time.Now()
for value := range *array {
count++
if value == lookingFor {
duration := time.Since(start)
fmt.Print("Simple search time: ")
fmt.Println(duration)
fmt.Println("Steps: " + strconv.Itoa(count))
return value, true
}
}
duration := time.Since(start)
fmt.Print("Simple search time: ")
fmt.Println(duration)
fmt.Println("Steps: " + strconv.Itoa(count))
return 0, false
}
Здесь все просто. Мы берем на входе в функцию тот же самый массив и число, которое нужно найти, проходим циклом по всему массиву с первого элемента по последний и сравниваем значение текущего элемента массива с полученным. Если оно совпадает — искомое найдено, возвращаем результат.
Обратите внимание, что здесь я добавил пару «плюшек». Во-первых, подсчет времени работы поиска. Считать я решил только время непосредственно поиска. Для этого хорошо подходит еще одна из особенность Go, а именно возможность считать время, прошеднее с взятой точки отсчета. Делается это так:
start := time.Now()
duration := time.Since(start)
fmt.Println(duration)
Здесь мы присваиваем переменной start текущее время, а затем получаем в переменную duration время, прошеднее с момента start. Причем встроенная в fmt функция печати понимает этот формат и выводит его в отформатированном виде: в наносекундах, милисекундах и так далее в зависимости от прошеднего времени. Это очень удобно, т.к. когда я в последний раз в академических целях занимался подсчетом времени работы функции в Java, я брал Unix timestamp и вручную высчитывал разницу, приводя ее к нужному формату.
Unix-время (англ. Unix time, также POSIX-время) — система описания моментов во времени, принятая в Unix и других POSIX-совместимых операционных системах. Определяется как количество секунд, прошедших с полуночи (00:00:00 UTC) 1 января 1970 года (четверг); этот момент называют «эпохой Unix» (англ. Unix Epoch).
Второй «плюшкой» я назвал подсчет количества шагов, потребовавшихся для достижения результата. Это просто переменная count, равная изначально нулю и инкрементируемая в теле цикла.
Не могу не сказать о том, что я немного поленился: вывод времени работы и количества шагов дублируется два раза, в теле цикла и перед финальным возвратом, вызываемым в случае отсутствия результата. Такое решение некрасиво и, по-хорошему, должно было бы быть вынесено в отдельную функцию, вызываемую в разных местах. Но здесь, думаю, простительно оставить в таком виде.
Теперь осталось добавить вызов второй функции в основном коде:
var simpleSearch, simpleResult = simpleSearch(&array, lookingFor)
if simpleResult {
fmt.Println("Found: " + strconv.Itoa(simpleSearch))
} else {
fmt.Println("Nothing found!")
}
Вызов аналогичен предыдущему, поэтому рассмаривать его подробно мы не станем.
Теперь полностью подготовленная программа выглядит так:
package main
import (
"fmt"
"strconv"
"time"
)
func main() {
var elems, lookingFor int
fmt.Print("Number of elements? ")
fmt.Scan(&elems)
var array = make([]int, elems)
start := time.Now()
for i := 0; i < elems; i++ {
array[i] = i
}
duration := time.Since(start)
fmt.Print("Time of generation: ")
fmt.Println(duration)
fmt.Println()
fmt.Println("What are we looking for:")
fmt.Scan(&lookingFor)
var binSearch, binResult = binarySearch(&array, lookingFor)
if binResult {
fmt.Println("Found: " + strconv.Itoa(binSearch))
} else {
fmt.Println("Nothing found!")
}
var simpleSearch, simpleResult = simpleSearch(&array, lookingFor)
if simpleResult {
fmt.Println("Found: " + strconv.Itoa(simpleSearch))
} else {
fmt.Println("Nothing found!")
}
}
func binarySearch(array *[]int, lookingFor int) (int, bool) {
var mid, assumption int
min := 0
high := len(*array) - 1
count := 0
start := time.Now()
for min <= high {
count++
mid = (min + high) / 2
assumption = mid
if assumption == lookingFor {
duration := time.Since(start)
fmt.Print("Binary search time: ")
fmt.Println(duration)
fmt.Println("Steps: " + strconv.Itoa(count))
return assumption, true
}
if assumption > lookingFor {
high = mid - 1
} else {
min = mid + 1
}
}
duration := time.Since(start)
fmt.Println("Steps: " + strconv.Itoa(count))
fmt.Print("Binary search time: ")
fmt.Println(duration)
return 0, false
}
func simpleSearch(array *[]int, lookingFor int) (int, bool) {
count := 0
start := time.Now()
for value := range *array {
count++
if value == lookingFor {
duration := time.Since(start)
fmt.Print("Simple search time: ")
fmt.Println(duration)
fmt.Println("Steps: " + strconv.Itoa(count))
return value, true
}
}
duration := time.Since(start)
fmt.Println("Steps: " + strconv.Itoa(count))
fmt.Print("Simple search time: ")
fmt.Println(duration)
return 0, false
}
Обратите внимание, что я добавил подсчет времени генерации исходного массива. Это не несет никакой полезной информации, просто заметил, что генерация массива с несколькими миллиардами элементов занимает довольно много времени, и решил замерить это время.
Найти исходные коды программы можно в репозитории.
Запуск и проверка работоспособности
Итак, давайте запустим программу и проверим наглядно, как правильный выбор алгоритма для какого-либо действия может сократить время, затрачиваемое машиной на решение задачи.
Обратите внимание, что время выполнения очень сильно зависит от того, на чем вы будете запускать программу. Причем не только от процессора, который и будет непосредственно выполнять все расчеты, но и от частоты шины, скорости работы оперативной памяти и так далее. Поэтому приведенные здесь цифры будут характерны только для моего ноутбука, в вашем случае результат может быть несколько иным (за исключением общей логики: что бинарный поиск быстрее и эффективнее, чем просто перебор элементов).
Далее приведены примеры работы с исходными массивами различного объема.
$ go run main.go
Number of elements? 10
Time of generation: 668ns
What are we looking for:
9
Binary search time: 518ns
Steps: 4
Found: 9
Simple search time: 424ns
Steps: 10
Found: 9
При размере исходного элемента в 10 элементов бинарный поиск занял немного больше времени, чем обычный, но при этом затрачено было в 2 раза меньше шагов. Это обсусловлено тем, что в бинарном поиске помимо операции сравнения присутствуют еще и дополнительные операции деления и присваивания новых границ оставшимся массивам. На них тоже нужно машинное время.
Также здесь может смутить момет, что на поиск числа 9 было потрачено 10 шагов, хотя мы изначально задавали размерность массива в 10 элементов. Это не ошибка. Причина в том, что в программировании (да и вообще во всем цифровом мире) отсчет начинается не с единицы, а с нуля. То есть массив с размерностью 10 элементов будет выглядеть так: 0 1 2 3 4 5 6 7 8 9. Если попытаться найти число 10, то мы получим ответ, что такого числа в массиве нет:
$ go run main.go
Number of elements? 10
Time of generation: 688ns
What are we looking for:
10
Steps: 4
Binary search time: 685ns
Nothing found!
Steps: 10
Simple search time: 585ns
Nothing found!
Также стоит заметить, что от положения искомого элемента в массиве тоже довольно сильно будет зависеть результат работы. Например, чтобы найти в отсортированном массиве число 1 нужно будет выполнить всего два шага простого поиска, тогда как бинарный займет немного больше времени. Поэтому для чистоты эксперимента я буду всегда искать последний элемент массива, т.к., как я уже говорил ранее, в теории алгоритмов всегда берется максимальная сложность, то есть подразумевается, что для простого поиска всегда нужно пройти по всем элементам массива.
Чтобы не перегружать статью тоннами одинакого выхлопа я решил свести все результаты работы в табличке:
| Количество элементов | Простой поиск | Бинарный поиск |
|---|---|---|
| 10, время генерации: 523ns | 398ns, Steps: 10 | 584ns, Steps: 4 |
| 100 время генерации: 5.92µs | 254ns, Steps: 100 | 449ns, Steps: 7 |
| 1000 время генерации: 10.16µs | 2.964µs, Steps: 1000 | 637ns, Steps: 10 |
| 1000000, время генерации: 6.278792ms | 1.731816ms, Steps: 1000000 | 828ns, Steps: 20 |
| 1000000000, время генерации: 2.335085339s | 616.497139ms, Steps: 1000000000 | 695ns, Steps: 30 |
Как видно из сравнения, эффективность бинарного поиска становится хорошо видна где-то после 1000 элементов. При этом время его работы даже с миллиардом элементов не превысило одной милисекунды, тогда как поиск простым перебором занял аж целых 620.
Выводы
Мы рассмотрели, что такое сложность алгоритмов, и почему важно обращать на нее внимание при разработке. На самом деле, основной мыслью, выносимой из этой статьи, помимо непосредственно теории и интересной практики, должна быть ментальная установка о том, что каждый ваш шаг как программиста должен сопровождаться размышлениями о том, чтобы сделать ваш код более эффективным. Да, можно сказать «Да нафига, железо щас мощное, вытянет!», но это в корне неверно. Мощности железа, несмотря на закон Мура, не являются гарантией того, что этих самых мощностей всегда будет хватать, как и поводом для того, чтобы плодить неээфективный код.