Если вы изучаете программирование, то рано или поздно столкнетесь с термином «О-нотация» или «Big O». Часто его подают как что-то сложное и математическое, но на самом деле это интуитивный инструмент, который помогает ответить на простой вопрос: «Насколько медленным или быстрым будет код при увеличении или уменьшении объема данных?»
Давайте разберемся без сложных формул.
- Аналогия из жизни: Доставка посылок
- Примеры на Go
- O(1) — Константная сложность
- O(n) — Линейная сложность
- O(n²) — Квадратичная сложность
- O(2ⁿ) — Экспоненциальная сложность
- O(log n) — Логарифмическая сложность
- O(n log n) — Линейно-логарифмическая сложность
- O(n!) — Факториальная сложность
- Почему это важно?
- Самый главный вывод
Аналогия из жизни: Доставка посылок
Представьте, что вы — курьер, и вам нужно развести посылки.
Задача 1: Доставить одну посылку в один дом. Сколько бы домов ни было в городе, вам нужно доставить только одну. Это займет постоянное время. В терминах О-нотации это О(1) — «константная сложность». Время выполнения не зависит от количества данных (домов).
Задача 2: Доставить по одной посылке в каждый из n домов на одной улице. Если домов станет в 2 раза больше, ваша работа займет в 2 раза больше времени. Это O(n) — «линейная сложность». Время выполнения растет прямо пропорционально объему данных.
Задача 3: Доставить по одной посылке в каждый дом, но обойти все улицы и переулки, проверяя каждый дом в городе. Если в городе n домов, вам в худшем случае придется проверить все n домов для каждой из n посылок. Это уже n * n операций. Если домов станет в 2 раза больше, работы станет в 4 раза больше. Это O(n²) — «квадратичная сложность». Время выполнения растет как квадрат от объема данных.
Суть О-нотации — описать, как в худшем случае будет вести себя алгоритм при изменении входных данных (обозначаемых как n).
Примеры на Go
Давайте посмотрим на конкретные примеры алгоритмов с разной сложностью.
O(1) — Константная сложность
Время выполнения не зависит от размера входных данных. Классический пример — доступ к элементу массива (слайса) по индексу.
package main
import "fmt"
func getFirstElement(slice []int) int {
return slice[0] // неважно, массив из 10 или 10 000 элементов
}
func main() {
someSlice := []int{15, 32, 48, 11, 79}
// всегда выполняется за константное время
fmt.Println(getFirstElement(someSlice))
}
O(n) — Линейная сложность
Время выполнения прямо пропорционально размеру данных. Пример — поиск элемента в неотсортированном массиве (в худшем случае).
package main
import "fmt"
func findValue(slice []int, target int) bool {
// цикл по всем n элементам
for _, value := range slice {
if value == target {
return true
}
}
return false
}
func main() {
someSlice := []int{15, 32, 48, 11, 79}
// в худшем случае пройдет все 5 элементов
fmt.Println(findValue(someSlice, 79))
// здесь тоже пройдет все 5 элементов, в итоге ничего не найдет
fmt.Println(findValue(someSlice, 18))
// здесь не все 5, но акцент на все равно на худшем случае
fmt.Println(findValue(someSlice, 48))
}
O(n²) — Квадратичная сложность
Время выполнения пропорционально квадрату размера данных. Пример — поиск дубликатов в неотсортированном массиве (в худшем случае).
package main
import "fmt"
func findDuplicate(slice []int) bool {
n := len(slice)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if slice[i] == slice[j] {
return true
}
}
}
return false
}
func main() {
someSlice := []int{15, 32, 48, 11, 79}
fmt.Println(findDuplicate(someSlice))
}
O(2ⁿ) — Экспоненциальная сложность
Характерна для задач, где на каждом шаге количество подзадач удваивается. Пример — нахождения числа Фибоначчи.
package main
import "fmt"
func fibonacci(n int) int {
if n <= 1 {
return n
}
// классический, но неэффективный подход
return fibonacci(n-1) + fibonacci(n-2)
}
func main() {
number := 6
fmt.Println(fibonacci(number)) // 8
}
O(log n) — Логарифмическая сложность
Время выполняется растет очень медленно. Пример — бинарный поиск.
package main
import "fmt"
func binarySearch(slice []int, target int) bool {
low, high := 0, len(slice)-1
for low <= high {
mid := (low + high) / 2
if slice[mid] == target {
return true
} else if slice[mid] < target {
low = mid + 1 // поиск в правой половине
} else {
high = mid - 1 // поиск в левой половине
}
}
return false
}
func main() {
sortedSlice := []int{8, 12, 15, 33, 49, 52, 67}
fmt.Println(binarySearch(sortedSlice, 52)) // true
fmt.Println(binarySearch(sortedSlice, 27)) // false
}
O(n log n) — Линейно-логарифмическая сложность
Часто встречается в эффективных алгоритмах сортировки. Пример — быстрая сортировка.
package main
import "fmt"
func quickSort(slice []int) []int {
if len(slice) < 2 {
return slice
}
pivot := slice[0]
var less, greater []int
for _, number := range slice[1:] {
if number <= pivot {
less = append(less, number)
} else {
greater = append(greater, number)
}
}
return append(append(quickSort(less), pivot), quickSort(greater)...)
}
func main() {
unsortedSlice := []int{12, 3, 17, 10, 53, 24, 1}
fmt.Println(quickSort(unsortedSlice)) // [1 3 10 12 17 24 53]
}
O(n!) — Факториальная сложность
Время выполнения растет как факториал от n. Пример — генерация всех перестановок.
package main
import "fmt"
func generatePermutations(slice []int) [][]int {
if len(slice) == 0 {
return [][]int{{}}
}
var result [][]int
for i := 0; i < len(slice); i++ {
rest := make([]int, 0, len(slice)-1)
rest = append(rest, slice[:i]...)
rest = append(rest, slice[i+1:]...)
for _, p := range generatePermutations(rest) {
permutation := append([]int{slice[i]}, p...)
result = append(result, permutation)
}
}
return result
}
func main() {
numbers := []int{1, 2, 3}
fmt.Println(generatePermutations(numbers))
// 3! = 1 * 2 * 3 = 6
// [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
}
Почему это важно?
Представьте, что у вас есть 1 000 000 записей в базе данных. Вам нужно выполнить конкретную задачу по обработке такого количества записей, соответственно:
- O(log n) — сделает всего около 20 операций
- O(n) — сделает ~ 1 000 000 операций
- O(n²) — сделает ~ 1 000 000 000 000 операций
- O(2ⁿ) — сделает ~ 2¹⁰⁰⁰⁰⁰⁰ операций (невычислимо)
- O(n!) — сделает ~ 1000000! операций (астрономическое число)
Понимание O-нотации помогает выбирать эффективные алгоритмы и структуры данных до написания кода, экономя время и ресурсы.
Самый главный вывод
- O-нотация — это мера скорости роста времени выполнения или потребления памяти алгоритма, а не точное время в секундах.
- Она описывает поведение в худшем случае.
- Константы и менее значимые слагаемые отбрасываются. Для больших n важно только то, что растет быстрее всего.
- Шкала эффективности (от лучшей к худшей):
- O(1) — идеально (константная)
- O(log n) — отлично (логарифмическая)
- O(n) — хорошо (линейная)
- O(n log n) — нормально (линейно-логарифмическая)
- O(n²) — плохо (квадратичная)
- O(2ⁿ) — очень плохо (экспоненциальная)
- O(n!) — очень очень плохо (факториальная)
Когда вы начнете анализировать свои циклы и вложенности, то совсем скоро вы автоматически будете чувствовать, насколько эффективен ваш код. Это ключевой навык для любого серьезного разработчика.
Напишите в комментариях, приходилось ли вам сталкиваться с задачами, где сложность алгоритма играла ключевую роль?
