Важные нюансы Big O

В этом уроке ты

Познакомишься со всеми основными оценками сложности
Узнаешь самые частые оценки сложности по времени и памяти
Научишься оставлять в Big O оценке только действительно важные параметры

Основные оценки сложности

В ходе курса мы уже разобрали такие оценки сложности, как O(1), O(n) и O(n*n). Но также есть ещё несколько популярных оценок:

O(1) — константная
O(log(n)) — логарифмическая (разберём в следующих уроках)
O(n) — линейная
O(n*log(n)) — линейно-логарифмическая (разберём в следующих уроках)
O(n*n) — квадратичная

Если в оценке сложности для одной и той же переменной есть несколько слагаемых разных порядков, оставляют только самое “большое”.

Например, в O(n*log(n) + n*n) достаточно записать O(n*n).

Но в O(n + m*log(m)) ничего убирать нельзя, так как n и m — разные переменные.

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

У каждой алгоритмической темы есть типичные оценки сложности, поэтому важно обращать внимание на сложность отдельно для каждой темы. Однако в общем виде самые распространённые варианты можно свести к следующей таблице:

Оценка	По времени	По памяти
O(1)	ОЧЕНЬ ЧАСТО	ОЧЕНЬ ЧАСТО
O(log(n))	РЕДКО	РЕДКО
O(n)	ОЧЕНЬ ЧАСТО	ОЧЕНЬ ЧАСТО
O(n*log(n))	РЕДКО	ОЧЕНЬ РЕДКО
O(n*n)	ЧАСТО	РЕДКО

Зависимость от нескольких параметров

// Время: O(n+m), где n - размер nums1, m - размер nums2
// Память: O(n+m), где n - размер nums1, m - размер nums2
using System.Collections.Generic;

public class Solution {
    public List<int> MergeArrays(List<int> nums1, List<int> nums2) {
        List<int> result = new List<int>();
        foreach (int num in nums1) {
            result.Add(num);
        }
        foreach (int num in nums2) {
            result.Add(num);
        }
        return result;
    }
}

// Время: O(n+m), где n - размер nums1, m - размер nums2
// Память: O(n+m), где n - размер nums1, m - размер nums2
#include <vector>

using namespace std;

vector<int> merge_arrays(const vector<int>& nums1, const vector<int>& nums2) {
    vector<int> result;
    for (int num : nums1) {
        result.push_back(num);
    }
    for (int num : nums2) {
        result.push_back(num);
    }
    return result;
}

// Время: O(n+m), где n - размер nums1, m - размер nums2
// Память: O(n+m), где n - размер nums1, m - размер nums2
func merge_arrays(nums1 []int, nums2 []int) []int {
    result := []int{}
    for _, num := range nums1 {
        result = append(result, num)
    }
    for _, num := range nums2 {
        result = append(result, num)
    }
    return result
}

// Время: O(n+m), где n - размер nums1, m - размер nums2
// Память: O(n+m), где n - размер nums1, m - размер nums2
import java.util.*;

public class Solution {
    public List<Integer> merge_arrays(List<Integer> nums1, List<Integer> nums2) {
        List<Integer> result = new ArrayList<>();
        for (int num : nums1) {
            result.add(num);
        }
        for (int num : nums2) {
            result.add(num);
        }
        return result;
    }
}

# Время: O(n+m), где n - размер nums1, m - размер nums2
# Память: O(n+m), где n - размер nums1, m - размер nums2
def merge_arrays(nums1: List[int], nums2: List[int]) -> List[int]:
    result = []
    for num in nums1:
        result.append(num)
    
    for num in nums2:
        result.append(num)
    return result

// Время: O(n+m), где n - размер nums1, m - размер nums2
// Память: O(n+m), где n - размер nums1, m - размер nums2
export function merge_arrays(nums1, nums2) {
    const result = [];
    for (const num of nums1) {
        result.push(num);
    }
    for (const num of nums2) {
        result.push(num);
    }
    return result;
}

Здесь время и память зависят от двух параметров: n (размер nums1) и m (размер nums2). Поэтому асимптотика — O(n+m).

Можно обозначить размеры по-разному, например O(x+y). Важно лишь пояснить, что x и y — это размеры соответствующих массивов.

Ещё один способ оценить тот же код — сказать, что время и память равны O(n), если n — общее число элементов в обоих массивах. Но на практике часто предпочитают именно O(n+m), чтобы подчеркнуть, что у нас два независимых источника данных.

Незначительные аргументы

// Время: O(n), где n - размер nums
// Память: O(1)
using System.Collections.Generic;

public class Solution {
    public List<int> SetK(List<int> nums, int k) {
        for (int i = 0; i < nums.Count; i++) {
            nums[i] = k;
        }
        return nums;
    }
}

// Время: O(n), где n - размер nums
// Память: O(1)
#include <vector>

using namespace std;

vector<int> set_k(vector<int>& nums, int k) {
    for (int i = 0; i < nums.size(); i++) {
        nums[i] = k;
    }
    return nums;
}

// Время: O(n), где n - размер nums
// Память: O(1)
func set_k(nums []int, k int) []int {
    for i := 0; i < len(nums); i++ {
        nums[i] = k
    }
    return nums
}

// Время: O(n), где n - размер nums
// Память: O(1)
import java.util.*;

public class Solution {
    public List<Integer> set_k(List<Integer> nums, int k) {
        for (int i = 0; i < nums.size(); i++) {
            nums.set(i, k);
        }
        return nums;
    }
}

# Время: O(n), где n - размер nums
# Память: O(1)
def set_k(nums: List[int], k: int) -> List[int]:
    for i in range(len(nums)):
        nums[i] = k
    return nums

// Время: O(n), где n - размер nums
// Память: O(1)
export function set_k(nums, k) {
    for (let i = 0; i < nums.length; i++) {
        nums[i] = k;
    }
    return nums;
}

В функции присутствует параметр k, который не влияет на итоговую оценку сложности. Это нормально! Часто в алгоритме есть параметры, не меняющие асимптотику. Однако не забывай, что в других задачах дополнительные параметры могут влиять на сложность — проверяй каждый случай.

Главные выводы

Есть пять наиболее частых оценок сложности: O(1), O(log(n)), O(n), O(n*log(n)) и O(n*n).
Если для одной переменной встречаются несколько слагаемых разного порядка, оставляют только самое большое (например, n*n + n оценивается как O(n*n)).
Оценка по времени и памяти может зависеть сразу от нескольких параметров, например O(n + m).
Некоторые параметры могут не влиять на оценку сложности.