Theta и Omega

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

Узнаешь, что такое Theta и Omega
Научишься проводить амортизационный анализ алгоритма

Знать Big O недостаточно

Не всегда Big O даёт полную картину о сложности алгоритма, ведь она описывает только худший случай. Если ты хочешь понять, как алгоритм работает в среднем или в самом лучшем случае, нужно использовать дополнительные обозначения — Theta и Omega.

Три кита оценки сложности

На практике чаще всего используют именно Big O, чтобы понять, насколько «плохо» может работать алгоритм. Theta и Omega так же используют, но намного реже.

Во многих простых алгоритмах Big O, Theta и Omega могут совпадать. Но в более сложных случаях (например, в быстрой сортировке quick sort) они отличаются.

Пример

Дан массив nums и число k. Нужно:

Если k = 1, вернуть сумму всех чисел в массиве.
Если k = 2, вернуть сумму первого и последнего элемента массива.
Если k отлично от 1 и 2, вернуть 0.

C вероятностью 90% при вызове функции k = 2.

using System.Collections.Generic;

public class Solution {
    public int FindSum(List<int> nums, int k) {
        if (k == 2) {
            return nums[0] + nums[nums.Count - 1];
        }
        if (k != 1) {
            return 0;
        }
        // k = 1
        int result = 0;
        foreach (int num in nums) {
            result += num;
        }
        return result;
    }
}

int find_sum(const std::vector<int>& nums, int k) {
    if (k == 2) {
        return nums[0] + nums[nums.size() - 1];
    }
    if (k != 1) {
        return 0;
    }
    // k = 1
    int result = 0;
    for (int num : nums) {
        result += num;
    }
    return result;
}

func find_sum(nums []int, k int) int {
    if k == 2 {
        return nums[0] + nums[len(nums)-1]
    }
    if k != 1 {
        return 0
    }
    // k = 1
    result := 0
    for _, num := range nums {
        result += num
    }
    return result
}

import java.util.*;

public class Solution {
    public int find_sum(List<Integer> nums, int k) {
        if (k == 2) {
            return nums.get(0) + nums.get(nums.size() - 1);
        }
        if (k != 1) {
            return 0;
        }
        // k = 1
        int result = 0;
        for (int num : nums) {
            result += num;
        }
        return result;
    }
}

def find_sum(nums: List[int], k: int) -> int:
    if k == 2:
        return nums[0] + nums[-1]
    if k != 1:
        return 0
    # k = 1
    result = 0
    for num in nums:
        result += num
    return result

export function find_sum(nums, k) {
    if (k === 2) {
        return nums[0] + nums[nums.length - 1];
    }
    if (k !== 1) {
        return 0;
    }
    // k = 1
    let result = 0;
    for (const num of nums) {
        result += num;
    }
    return result;
}

Теперь оценим сложность программы в Big O, Theta и Omega. Пусть n — размер массива nums:

	Время	Память	Объяснение
Big O	O(n)	O(1)	Худший случай: когда `k = 1`, нужно суммировать все `n` элементов массива.
Theta	Θ(1), если k≠1,Θ(n), если k=1	Θ(1)	Реальная оценка: с вероятностью 90% `k = 2`, и мы складываем только первый и последний элементы.
Omega	Ω(1)	Ω(1)	Лучший случай: если `k = 2` (или `k != 1`), нам не нужно суммировать весь массив.

Амортизационный анализ

Амортизационный анализ — это метод, который рассматривает среднее время выполнения операций за серию действий, а не за одну операцию.

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

Например, обычная вставка в хеш-таблицу занимает O(1), но при переполнении нужно сделать rehash всех элементов → это O(n). Однако, такое событие происходит редко, поэтому амортизированная сложность вставки остаётся O(1).

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

Помимо Big O, есть Theta и Omega, которые оценивают точный и лучший случаи соответственно.
Амортизационный анализ применяют там, где отдельные операции могут быть дорогими, но в среднем они оказываются дешевле.