Сложность алгоритма - это количественная характеристика, которая говорит о том, сколько времени, либо какой объём памяти потребуется для выполнения алгоритма.
Развитие технологий привело к тому, что память перестала быть критическим ресурсом. Поэтому когда говорят об анализе сложности алгоритма, обычно подразумевают то, насколько быстро он работает.
Но ведь время выполнения алгоритма зависит от того, на каком устройстве его запустить. Один и тот же алгоритм запущенный на разных устройствах выполняется за разное время.
Тогда было предложено измерять сложность алгоритмов в элементарных шагах - то, сколько действий необходимо совершить для его выполнения. Любой алгоритм включает в себя определённое количество шагов и не важно на каком устройстве он будет запущен, количество шагов останется неизменным. Эту идею принято представлять в виде Big O (или О-нотации).
Big O показывает то, как сложность алгоритма растёт с увеличением входных данных. При этом она всегда показывает худший вариант развития событий - верхнюю границу.
Big O показывает верхнюю границу зависимости между входными параметрами функции и количеством операций, которые выполнит процессор.
Распространённые сложности алгоритмов
Здесь рассмотрены именно распространённые виды, так как рассмотреть все варианты врядли возможно. Всё зависит от алгоритма, который вы оцениваете. Всегда может появится какая-то дополнительная переменная (не константа), которую необходимо будет учесть в функции Big O.
Константная - O(1).
Означает, что вычислительная сложность алгоритма не зависит от входных данных. Однако, это не значит, что алгоритм выполняется за одну операцию или требует очень мало времени. Это означает, что время не зависит от входных данных.
Пример № 1.
У нас есть массив из 5 чисел и нам надо получить первый элемент.
1
2
val nums = intArrayOf(1, 2, 3, 4, 5)
val firstNumber = nums[0]
Насколько возрастет количество операций при увеличении размера входных параметров?
Нинасколько. Даже если массив будет состоять из 100, 1000 или 10 000 элементов нам всеравно потребуется одна операция.
Пример № 2.
Сложение двух чисел. Функция всегда выполняет константное количество операций.
1
fun pairSum(a: Int, b: Int) = a + b
Пример № 3.
Размер массива. Опять же, функция всегда выполняет константной количество операций.
1
fun getSize(nums: List<Int>): Int = nums.size
Линейная - O(n).
Означает, что сложность алгоритма линейно растёт с увеличением входных данных. Другими словами, удвоение размера входных данных удвоит и необходимое время для выполнения алгоритма.
Такие алгоритмы легко узнать по наличию цикла по каждому элементу массива.
Пример № 1 - Рекурсивная функция.
1
2
3
4
fun sum(n: Int): Int {
if (n == 1) return 1
return n + sum(n - 1)
}
Пример № 2 - Линейная функция.
1
2
3
4
5
6
7
8
9
fun pairSumSequence(n: Int): Int {
var sum = 0
for (i in 0 until n) {
sum += pairSum(i, i + 1)
}
return sum
}
fun pairSum(a: Int, b: Int) = a + b
Функция pairSumSequence() в цикле складывает какие-либо пары чисел, вызывая функцию pairSum(). Цикл выполняется от 0 до n. Т.е. чем больше n, тем больше раз выполнится цикл. Поэтому сложность функции pairSumSequence() - O(n).
Пример № 3.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
fun sum(nums: List<Int>) {
var sum = 0
var product = 1
for(num in nums) {
sum += num
}
for(num in nums) {
product *= num
}
println(sum, product)
}
В функции два последовательных цикла for, каждый из которых проходит массив длиной n, следовательно сложность будет: O(n + n) = O(n)
Логарифмическая - O(log n).
Означает, что сложность алгоритма растёт логарифмически с увеличением входных данных. Другими словами это такой алгоритм, где на каждой итерации берётся половина элементов.
К алгоритмам с такой сложностью относятся алгоритмы типа “Разделяй и Властвуй” (Divide and Conquer), например бинарный поиск.
Линеарифметическая или линеаризованная - O(n * log n).
Означает, что удвоение размера входных данных увеличит время выполнения чуть более, чем вдвое.
Примеры алгоритмов с такой сложностью: Сортировка слиянием или множеством n элементов.
Квадратичная - O(n2), O(n^2).
Означает, что удвоение размера входных данных увеличивает время выполнения в 4 раза. Например, при увеличении данных в 10 раз, количество операций (и время выполнения) увеличится примерно в 100 раз. Если алгоритм имеет квадратичную сложность, то это повод пересмотреть необходимость использования данного алгоритма. Но иногда этого не избежать.
Такие алгоритмы легко узнать по вложенным циклам.
Пример № 1.
1
2
3
4
5
6
7
fun printPairs(nums: List<Int) {
for (i in nums) {
for (j in nums) {
println(nums[i], nums[j])
}
}
}
В функции есть цикл в цикле, каждый из них проходит массив длиной n, следовательно сложность будет: O(n * n) = O(n2)
Зачем изучать Big O
- Концепцию Big O необходимо понимать, чтобы уметь видеть и исправлять неоптимальный код.
- Ни один серьёзный проект, как ни одно серьёзное собеседование, не могут обойтись без вопросов о Big O.
- Непонимание Big O ведёт к серьёзной потере производительности ваших алгоритмов.
Шпаргалка
Небольшие подсказки, которые помогут определить сложность алгоритма.
- Получение элемента коллекции это O(1). Будь то получение по индексу в массиве, или по ключу в словаре в нотации Big O это будет O(1).
- Перебор коллекции это O(n).
- Вложенные циклы по той же коллекции это O(n2).
- Разделяй и властвуй (Divide and Conquer) всегда O(log n).
- Итерации которые используют “Разделяй и властвуй” (Divide and Conquer) это O(n log n).
Полезные ссылки
Оценка сложности алгоритма. Сложность алгоритмов. Big O, Большое О - 25-минутное видео, в котором очень доступно (и с примерами) объясняются основы анализа сложности алгоритмов.
Big O - статья на хабре о Big O.
Знай сложности алгоритмов - статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов.