Оценка сложности

Оценка сложности - это подход, который позволяет оценить время или память, нужные алгоритму, в зависимости от размера входных данных, независимо от компьютера, языка программирования и компилятора.

Оценка сложности используется для понимания различий алгоритмов и для выбора наиболее подходящего под конкретные требования и ограничения. Зачастую рассматривается худший случай (входные данные, на которых алгоритм ведет себя хуже всего), хотя также бывает важно понимать поведение в среднем случае.

В разговоре можно слышать следующие синонимы: алгоритмическая сложность, вычислительная сложность, трудоемкость алгоритма, асимптотическая сложность, большое "О".

В этой статье мы разберем основные понятия и подходы к оценке сложности, необходимые для интервью. Мы не будем сильно вдаваться в нюансы и тонкости, такие как "о малое" и "омега малое".

Если вы захотите погрузиться в тему подробнее, смотрите следующие книги:

• Глава 3. Рост функций, Алгоритмы. Построение и анализ | Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн
• Глава 2. Анализ алгоритмов, Алгоритмы. Руководство по разработке | Стивен Скиена

Зачем нужно делать оценку сложности?

Основные причины, по которым нужно оценивать сложность алгоритмов:

• Прогнозирование производительности - понимание того, как замедлится работа программы при увеличении объема входных данных (массивов, баз данных).

• Сравнение алгоритмов - возможность выбрать оптимальный алгоритм из нескольких вариантов для одной задачи без необходимости писать и тестировать код каждого из них.

• Оптимизация ресурсов - выявление узких мест, где алгоритм потребляет слишком много времени или памяти и поиск более эффективных решений.

• Масштабируемость - уверенность в том, что система продолжит корректно работать, если количество пользователей или объем данных вырастет в 10, 100 или 1000 раз.

• Абстракция от железа - оценка принципиальной сложности, не зависящая от мощности компьютера.

Почему недостаточно замеров?

Мы могли бы замерить время работы кода или потребляемую память, например используя инструмент профилирования кода программы.

Замеры (бенчмарки) зависят от конкретного компьютера, языка программирования, операционной системы, версии рантайма и многих других факторов. Кроме того, такие замеры придется делать для большого набора входных данных, чтобы понять поведение алгоритма при росте данных.

Давайте проясним: бенчмарки полезны и важны, и на практике их часто используют, но нам также важно еще до написания кода понимать ограничения и поведение алгоритма при росте входных данных. Мы бы хотели иметь некий абстрактный способ оценивать и сравнивать алгоритмы.

Асимптотическая нотация

Для оценки сложности очень часто используется асимптотическая нотация Big O, или "O большое". Это оценка количества операций или ячеек памяти как функции от размера входных данных. Она дает понимание эффективности алгоритма.

Например, если сложность алгоритма O(n^2) (читается как "О большое от эн квадрат"), то при увеличении данных в 10 раз время работы вырастет примерно в 100 раз, независимо от быстродействия процессора. Если входные данные вырастут в 100 раз, то время работы вырастет в 10000 раз, и мы сразу видим, что такой алгоритм непригоден на больших нагрузках.

Временная и пространственная сложность

В контексте алгоритмической сложности "время" обозначает объем вычислений, а "пространство" - объем памяти, необходимый алгоритму для завершения своей работы.

Временная сложность определяет время выполнения в зависимости от размера входных данных. Пространственная сложность определяет объем памяти, занимаемый алгоритмом для выполнения, в зависимости от размера входных данных.

Важно отметить, что время и пространство часто конкурируют друг с другом: оптимизация алгоритма для повышения его скорости часто требует увеличения объема памяти, а уменьшение использования памяти может привести к замедлению работы алгоритма. Это известно как компромисс между пространством и временем.

Временная сложность

Временная сложность алгоритма зависит от всех операций, необходимых для его выполнения.

Как вычисляется временная сложность?

Пример:

оператор 1: int a = b; // чтение b и присваивание в a
оператор 2: if (a == 2) // сравнение
оператор 3:   return true; // оператор return
оператор 4: int x = a > 5 ? 1 : 0; // чтение a, сравнение, присваивание x
...
...
оператор N: ...

В этом примере мы могли бы вычислить общее время работы как:

общее время = время(оператор 1) +
              время(оператор 2) +
              время(оператор 3) +
              время(оператор 4) +
              ... +
              время(оператор N)

Пусть n - это размер входных данных, обозначим общее время как T(n), а время выполнения базового оператора как t:

T(n) = t(оператор 1) + t(оператор 2) + ... + t(оператор N);

Если все наши операторы выполняют некоторое небольшое константное число элементарных операций, таких как сравнения, присваивания, чтения и записи переменных, то мы можем считать, что каждый из операторов занимает некоторое постоянное время, то есть t = O(1).

Таким образом мы можем абстрагироваться от конкретного времени выполнения разных операторов и тогда Т(n) - это будет уже не время в минутах или секундах, а абстрактное число операций.

В таком подходе мы принимаем некоторую модель вычислений (в данном случае модель вычислений RAM-машины) и уходим от конкретного железа и модели процессора.

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

Рассмотрим пример:

for i := 0; i < n; i++ {
    print(i)
}

Для цикла мы вычисляем время выполнения блока внутри него и умножаем его на количество повторений цикла.

Цикл выполнится n раз и выведет на экран числа от 0 до n-1. Мы считаем print как базовый оператор, которому требуется какое-то константное время исполнения c, то есть t(print i) = c = O(1). Таким образом, время выполнения этой программы составит:

T(n) = n * t(print i)
     = n * c
     = n * O(1)
     = O(n)

Это так называемая линейная сложность - то есть при увеличении размера входных данных n - сложность увеличивается линейно по отношению к n (пропорционально n).

Пространственная сложность

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

Как вычисляется пространственная сложность?

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

Простые переменные занимают O(1) памяти. Если нам нужно создать массив размером n, это потребует O(n) памяти. Если мы создадим двумерный массив размером n * n, это потребует O(n^2) памяти.

Также важно помнить, что в случае рекурсивных вызовов мы можем тратить память на каждый рекурсивный вызов.

Пример:

func factorial(n int) int {
	if n <= 0 {
		return 1
	}
	return n * factorial(n-1)
}

При выполнении такая функция будет делать рекурсивные вызовы:

1.  factorial(4)
2.    -> factorial(3)
3.      -> factorial(2)
4.        -> factorial(1)
5.          -> factorial(0)

Каждый из таких вызовов будет добавляться на стек исполнения и будет занимать реальную память. Таким образом суммарно это потребует O(n) памяти.

func add(n int) int {
	sum := 0
	for i := 0; i < n; i++ {
		sum += double(i)
	}
	return sum
}
 
func double(x int) int {
return 2 \* x
}
 

Примеры нотации O большое

Кроме линейной сложности приведем примеры других вариантов сложности в терминах "О большое".

Константная сложность

Константная временная сложность O(1) означает, что время выполнения алгоритма никак не зависит от размера входных данных и равно некоторому постоянному времени. Например, запись элемента в массив по указанному индексу имеет O(1) сложность.

Также сложность чтения или записи в хеш-таблицах обычно считается равной O(1). Это делает их одной из самых быстрых структур данных. Этот показатель достигается за счет вычисления хеш-функции, которая напрямую указывает на местоположение элемента.

Логарифмическая сложность

Логарифмическая временная сложность O(log n) означает, что время выполнения алгоритма пропорционально логарифму от размера входных данных.

Например, алгоритм бинарного поиска имеет логарифмическую временную сложность:

func binarySearch(arr []int, x int) int {
	l := 0
	r := len(arr) - 1
	for r >= l {
		mid := l + (r-l)/2
		if arr[mid] == x {
			return mid
		}
		if arr[mid] > x {
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	return -1
}

Линейная сложность

Линейная временная сложность O(n) означает, что время выполнения алгоритма линейно возрастает с размером входных данных. Например, рассмотрим алгоритм, который проходит по массиву, чтобы найти определенный элемент.

func find(arr []int, key int) bool {
	n := len(arr)
	for i := 0; i < n; i++ {
		if arr[i] == key {
			return true
		}
	}
	return false
}

Квадратичная сложность

Квадратичная временная сложность O(n^2) означает, что время выполнения алгоритма пропорционально квадрату размера входных данных. Например, простой алгоритм сортировки пузырьком имеет квадратичную временную сложность.

func bubbleSort(arr []int) {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		for j := 0; j < n-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

Кубическая сложность

Кубическая временная сложность O(n^3) означает, что время выполнения алгоритма пропорционально кубу размера входных данных. Например, наивный алгоритм умножения матриц имеет кубическую временную сложность.

func multiply(mat1, mat2 [][]int) [][]int {
	N := len(mat1)
 
    res := make([][]int, N)
    for i := range res {
    	res[i] = make([]int, N)
    }
 
    for i := 0; i < N; i++ {
    	for j := 0; j < N; j++ {
    		for k := 0; k < N; k++ {
    			res[i][j] += mat1[i][k] * mat2[k][j]
    		}
    	}
    }
    return res
 
}
 

Полиномиальная сложность

Полиномиальная временная сложность - это временная сложность алгоритма, которая может быть выражена в виде полиномиальной функции от размера входных данных n. В нотации "О большое" алгоритм считается полиномиальным, если его временная сложность равна O(n ^ k), где степень полинома k - константа.

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

К распространенным примерам алгоритмов с полиномиальной временной сложностью относятся линейная временная сложность O(n), квадратичная временная сложность O(n ^ 2) и кубическая временная сложность O(n ^ 3).

Экспоненциальная сложность

Экспоненциальная временная сложность, например O(2 ^ n), означает, что время выполнения алгоритма удваивается с каждым добавлением элемента в набор входных данных.

Например, задача генерации всех подмножеств множества имеет экспоненциальную временную сложность O(2 ^ n):

func generateSubsets(arr []int) {
	n := len(arr)
    // Существует 2 ^ n возможных подмножеств, (1 << n)
	m := 1 << n
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
            // Проверка выставлен ли j-й бит
			if (i & (1 << j)) != 0 {
				fmt.Printf("%d ", arr[j])
			}
		}
		fmt.Println()
	}
}

Факториальная сложность

Факториальная временная сложность O(n!) означает, что время выполнения алгоритма возрастает факториально с размером входных данных. Это часто наблюдается в алгоритмах, которые генерируют все перестановки набора данных.

Вот пример алгоритма с факториальной временной сложностью, который генерирует все перестановки массива:

func permute(a []int, l, r int) {
	if l == r {
		for i := 0; i <= r; i++ {
			fmt.Printf("%d ", a[i])
		}
		fmt.Println()
	} else {
		for i := l; i <= r; i++ {
			a[l], a[i] = a[i], a[l]
			permute(a, l+1, r)
			a[l], a[i] = a[i], a[l] // backtrack
		}
	}
}