Big O нотация
Что такое Big O?
Big O нотация — это математический способ описать верхнюю границу роста времени выполнения или потребления памяти алгоритма в зависимости от размера входных данных.
Проще говоря, Big O отвечает на вопрос: «Как изменится время работы, если входных данных станет в 10 раз больше?»
Зачем это нужно?
- Сравнивать алгоритмы между собой объективно
- Предсказывать поведение на больших данных
- Принимать обоснованные инженерные решения
- Говорить на одном языке с другими разработчиками
Основные классы сложности
O(1) — константная сложность
Время выполнения не зависит от размера входных данных.
PHPGo
// Access array element by index
function getFirst(array $arr): mixed
{
return $arr[0]; // Always one operation
}
// Access associative array element by key
function getValue(array $map, string $key): mixed
{
return $map[$key]; // Average O(1)
}
// Access slice element by index
func getFirst(arr []int) int {
return arr[0] // Always one operation
}
// Access map element by key
func getValue(m map[string]int, key string) int {
return m[key] // Average O(1)
}
O(log n) — логарифмическая сложность
На каждом шаге отбрасывается половина данных. Очень эффективно!
PHPGo
// Binary search
function binarySearch(array $arr, int $target): int
{
$left = 0;
$right = count($arr) - 1;
while ($left <= $right) {
$mid = intdiv($left + $right, 2);
if ($arr[$mid] === $target) {
return $mid;
} elseif ($arr[$mid] < $target) {
$left = $mid + 1;
} else {
$right = $mid - 1;
}
}
return -1;
}
// Binary search
func binarySearch(arr []int, target int) int {
left, right := 0, len(arr)-1
for left <= right {
mid := (left + right) / 2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
O(n) — линейная сложность
Время растёт пропорционально размеру входных данных.
PHPGo
// Find maximum in array
function findMax(array $arr): int
{
$maxVal = $arr[0];
foreach ($arr as $num) { // Go through each element
if ($num > $maxVal) {
$maxVal = $num;
}
}
return $maxVal;
}
// Sum of elements
function total(array $arr): int
{
return array_sum($arr); // Single pass through array
}
// Find maximum in slice
func findMax(arr []int) int {
maxVal := arr[0]
for _, num := range arr { // Go through each element
if num > maxVal {
maxVal = num
}
}
return maxVal
}
// Sum of elements
func total(arr []int) int {
sum := 0
for _, v := range arr { // Single pass through slice
sum += v
}
return sum
}
O(n log n) — линеарифмическая сложность
Типичная сложность эффективных сортировок. Каждый из n элементов обрабатывается log n раз.
PHPGo
// Merge sort
function mergeSort(array $arr): array
{
if (count($arr) <= 1) {
return $arr;
}
$mid = intdiv(count($arr), 2);
$left = mergeSort(array_slice($arr, 0, $mid)); // log n levels
$right = mergeSort(array_slice($arr, $mid)); // of recursion
return merge($left, $right); // n operations per level
}
function merge(array $left, array $right): array
{
$result = [];
$i = 0;
$j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] <= $right[$j]) {
$result[] = $left[$i];
$i++;
} else {
$result[] = $right[$j];
$j++;
}
}
while ($i < count($left)) {
$result[] = $left[$i++];
}
while ($j < count($right)) {
$result[] = $right[$j++];
}
return $result;
}
// Merge sort
func mergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
left := mergeSort(arr[:mid]) // log n levels
right := mergeSort(arr[mid:]) // of recursion
return merge(left, right) // n operations per level
}
func merge(left, right []int) []int {
result := make([]int, 0, len(left)+len(right))
i, j := 0, 0
for i < len(left) && j < len(right) {
if left[i] <= right[j] {
result = append(result, left[i])
i++
} else {
result = append(result, right[j])
j++
}
}
result = append(result, left[i:]...)
result = append(result, right[j:]...)
return result
}
O(n²) — квадратичная сложность
Вложенные циклы — каждый элемент сравнивается с каждым.
PHPGo
// Bubble sort
function bubbleSort(array $arr): array
{
$n = count($arr);
for ($i = 0; $i < $n; $i++) { // n iterations
for ($j = 0; $j < $n - 1 - $i; $j++) { // another n iterations
if ($arr[$j] > $arr[$j + 1]) {
[$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
}
}
}
return $arr;
}
// Check for duplicates (naive approach)
function hasDuplicateNaive(array $arr): bool
{
$n = count($arr);
for ($i = 0; $i < $n; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
if ($arr[$i] === $arr[$j]) {
return true;
}
}
}
return false;
}
// Bubble sort
func bubbleSort(arr []int) []int {
n := len(arr)
for i := 0; i < n; i++ { // n iterations
for j := 0; j < n-1-i; j++ { // another n iterations
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
return arr
}
// Check for duplicates (naive approach)
func hasDuplicateNaive(arr []int) bool {
n := len(arr)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if arr[i] == arr[j] {
return true
}
}
}
return false
}
O(2^n) — экспоненциальная сложность
Удваивается на каждом шаге. Быстро становится неприемлемо.
PHPGo
// Naive Fibonacci
function fib(int $n): int
{
if ($n <= 1) {
return $n;
}
return fib($n - 1) + fib($n - 2); // Two recursive calls!
}
// Naive Fibonacci
func fib(n int) int {
if n <= 1 {
return n
}
return fib(n-1) + fib(n-2) // Two recursive calls!
}
Сравнение сложностей: ASCII-график
Время
|
| O(2^n)
| *
| *
| *
| * O(n²)
| * *
| *
| * *
| * O(n log n)
| * * *
| * * *
| * * * * O(n)
| * * * *
| * * * O(log n)
|* * *
|* * * * * * * * * * * * * * * * * * * * * O(1)
+----------------------------------------------------> n
1 2 4 8 16 32 64 128 256 512
Таблица сравнения
| Big O | Название | n=10 | n=100 | n=1000 | n=1 000 000 |
|---|---|---|---|---|---|
| O(1) | Константная | 1 | 1 | 1 | 1 |
| O(log n) | Логарифмическая | 3 | 7 | 10 | 20 |
| O(n) | Линейная | 10 | 100 | 1 000 | 1 000 000 |
| O(n log n) | Линеарифмическая | 33 | 664 | 9 966 | 19 931 569 |
| O(n²) | Квадратичная | 100 | 10 000 | 1 000 000 | 10^12 |
| O(2^n) | Экспоненциальная | 1 024 | 10^30 | 10^301 | ... |
Правила определения Big O
Правило 1: Отбрасываем константы
PHPGo
// This is all O(n), despite different number of passes
function example(array $arr): void
{
foreach ($arr as $x) { // n
echo $x . "\n";
}
foreach ($arr as $x) { // n
echo $x . "\n";
}
foreach ($arr as $x) { // n
echo $x . "\n";
}
}
// Total: 3n -> O(n)
// This is all O(n), despite different number of passes
func example(arr []int) {
for _, x := range arr { // n
fmt.Println(x)
}
for _, x := range arr { // n
fmt.Println(x)
}
for _, x := range arr { // n
fmt.Println(x)
}
}
// Total: 3n -> O(n)
PHPGo
function example(array $arr): void
{
// O(n)
foreach ($arr as $x) {
echo $x . "\n";
}
// O(n²)
foreach ($arr as $i) {
foreach ($arr as $j) {
echo "$i $j\n";
}
}
}
// Total: O(n) + O(n²) = O(n²)
func example(arr []int) {
// O(n)
for _, x := range arr {
fmt.Println(x)
}
// O(n²)
for _, i := range arr {
for _, j := range arr {
fmt.Printf("%d %d\n", i, j)
}
}
}
// Total: O(n) + O(n²) = O(n²)
PHPGo
function process(array $arrA, array $arrB): void
{
foreach ($arrA as $a) { // O(a)
echo $a . "\n";
}
foreach ($arrB as $b) { // O(b)
echo $b . "\n";
}
}
// Total: O(a + b), NOT O(n)!
function cross(array $arrA, array $arrB): void
{
foreach ($arrA as $a) {
foreach ($arrB as $b) {
echo "$a $b\n";
}
}
}
// Total: O(a * b)
func process(arrA, arrB []int) {
for _, a := range arrA { // O(a)
fmt.Println(a)
}
for _, b := range arrB { // O(b)
fmt.Println(b)
}
}
// Total: O(a + b), NOT O(n)!
func cross(arrA, arrB []int) {
for _, a := range arrA {
for _, b := range arrB {
fmt.Printf("%d %d\n", a, b)
}
}
}
// Total: O(a * b)
PHPGo
// Each time we halve n -> O(log n)
function halve(int $n): void
{
while ($n > 1) {
$n = intdiv($n, 2);
}
}
// Each time we halve n -> O(log n)
func halve(n int) {
for n > 1 {
n = n / 2
}
}
Типичные лимиты для задач на LeetCode/интервью (при ~10^8 операций в секунду):
| Размер n | Допустимая сложность |
|---|---|
| n ≤ 10 | O(n!), O(2^n) |
| n ≤ 20 | O(2^n) |
| n ≤ 500 | O(n³) |
| n ≤ 10 000 | O(n²) |
| n ≤ 1 000 000 | O(n log n) |
| n ≤ 10^8 | O(n) |
| n > 10^8 | O(log n), O(1) |
Запомни: Если на интервью дали n = 10^5, значит ожидается решение O(n log n) или лучше. Если n = 10^3 — подойдёт O(n²).
Частые ошибки
Ошибка 1: «O(2n) — это O(2n)»
Нет! O(2n) = O(n). Константы не имеют значения в Big O.
Ошибка 2: «Рекурсия = O(n)»
Не обязательно. Рекурсия с двумя ветвлениями может быть O(2^n).
Ошибка 3: Путать лучший, средний и худший случай
Big O обычно описывает худший случай (worst case). Но для хеш-таблиц мы часто говорим о среднем (amortized).
Amortized Analysis (Амортизированный анализ)
Некоторые операции обычно быстрые, но иногда медленные:
PHPGo
// Dynamic array: append is usually O(1)
// But when array is full — copying O(n)
// Amortized: O(1) per operation
$arr = [];
for ($i = 0; $i < 1000000; $i++) {
$arr[] = $i; // Amortized O(1)
}
// Dynamic slice: append is usually O(1)
// But when capacity is full — copying O(n)
// Amortized: O(1) per operation
arr := make([]int, 0)
for i := 0; i < 1000000; i++ {
arr = append(arr, i) // Amortized O(1)
}
Итоги
- Big O показывает как масштабируется алгоритм
- Отбрасывайте константы и младшие члены
- Разные входы — разные переменные
- Деление пополам = log n
- Вложенные циклы умножают сложность
- На интервью: смотри на ограничения n, чтобы понять ожидаемую сложность