Към съдържанието
wannacode

Амортизирана сложност

Накратко: Амортизираната сложност е средната цена на операция в дълга поредица: добавянето в динамичен масив понякога копира всичко, но щом масивът расте с множител (например ×2), е средно O(1).

Проблем

Вносът, който копира всичко

Магазинът внася поръчките от стара система по една. Някой е написал вноса така, че при всяка поръчка масивът става с едно място по-голям:

static long ImportOrders(int n)
{
    int[] orders = new int[0];
    long copies = 0;
    for (int i = 0; i < n; i++)
    {
        copies += orders.Length;
        Array.Resize(ref orders, orders.Length + 1);
        orders[^1] = 100000 + i;
    }
    return copies;
}

Изглежда невинно: един ред на поръчка. Но всеки нов масив е копие на стария плюс едно място. Програмата брои копиранията:

foreach (int n in new[] { 1000, 10000 })
{
    Console.WriteLine(n + " поръчки: " + ImportOrders(n) + " копирания");
}
Изход
1000 поръчки: 499500 копирания
10000 поръчки: 49995000 копирания

При 10 пъти повече поръчки копиранията са 100 пъти повече. При 100 000 поръчки са 4 999 950 000, и вносът, който на теста трае миг, сега върви с минути. А List.Add на същите 100 000 поръчки свършва веднага, макар че и той понякога копира целия масив. Как?

Идеята

Списъкът не расте с едно място

Отвътре списъкът е масив с повече места, отколкото елементи. Когато се напълни, прави нов, по-голям масив и копира всичко в него:

List<string> cart = new List<string>(3);
cart.Add("Хляб");
cart.Add("Мляко");
cart.Add("Кафе");
cart.Add("Масло");
cart.Remove("Мляко");
Console.WriteLine(string.Join(", ", cart));
Console.WriteLine("Продукти: " + cart.Count);
Стъпка по стъпка, с думи
  1. cart сочи обект List<string>. Вътре има масив _items с 3 места и брояч _size.
  2. Add слага всеки елемент на първото свободно място и увеличава _size.
  3. Масивът е пълен. List<T> прави нов с 6 места, двойно повече, и копира трите елемента в него.
  4. _items вече сочи новия масив, а старият не трябва на никого. „Масло“ влиза на свободното място.
  5. Remove маха „Мляко“, а всичко след него се мести с едно място наляво. Дупка не остава.
  6. Отвън се вижда само списък с три продукта: копирането и местенето ги прави List<T>. Колко места има, казва Capacity.

Тайната е колко по-голям е новият масив. Ако е с едно място повече, всяко добавяне след пълния масив копира всичко, както вносът горе. Ако е два пъти по-голям, следващото копиране идва чак след още толкова добавяния.

Виж го

Свой масив, който се удвоява

Ето същият механизъм, написан на ръка, с брояч на копиранията. Масивът започва с едно място:

class OrderList
{
    private int[] items = new int[1];
    private int size = 0;
    public long Copies { get; private set; }


    public void Add(int order)
    {
        if (size == items.Length)
        {
            int[] bigger = new int[items.Length * 2];
            for (int i = 0; i < size; i++)
            {
                bigger[i] = items[i];
                Copies++;
            }
            items = bigger;
        }
        items[size] = order;
        size++;
    }
}
foreach (int n in new[] { 9, 1000 })
{
    var orders = new OrderList();
    for (int i = 0; i < n; i++)
    {
        orders.Add(100000 + i);
    }
    Console.WriteLine(n + " поръчки: " + orders.Copies + " копирания" + ", 2n = " + 2 * n);
}
Изход
9 поръчки: 15 копирания, 2n = 18
1000 поръчки: 1023 копирания, 2n = 2000

class OrderList
{
    private int[] items = new int[1];
    private int size = 0;
    public long Copies { get; private set; }


    public void Add(int order)
    {
        if (size == items.Length)
        {
            int[] bigger = new int[items.Length * 2];
            for (int i = 0; i < size; i++)
            {
                bigger[i] = items[i];
                Copies++;
            }
            items = bigger;
        }
        items[size] = order;
        size++;
    }
}


var orders = new OrderList();
for (int i = 0; i < 9; i++)
{
    orders.Add(100000 + i);
}
Стъпка по стъпка, с думи
  1. Масивът започва с едно място, а size е 0. Броим само копиранията на стари елементи.
  2. Първата поръчка: има място, Add я записва. Копирания: 0.
  3. Втората: масивът е пълен. Нов масив с 2 места, а старата поръчка се копира в него: 1 копиране.
  4. Третата: пак е пълно, 4 места и 2 копирания. Четвъртата влиза без копиране.
  5. Петата копира 4, деветата 8. Копиранията растат, но между тях идват все повече добавяния без копиране.
  6. 9 добавяния, 1 + 2 + 4 + 8 = 15 копирания, под 2n = 18. Разпределени по всички добавяния, са под 2 на добавяне: O(1) амортизирано.

Добавяне, което намери масива пълен, копира всичко: 1, 2, 4, 8, 16 … Но след него идват толкова добавяния без копиране, колкото е копирало. Сборът 1 + 2 + 4 + … + 2ᵏ е винаги под 2 · 2ᵏ, а последното копиране 2ᵏ е под n. Значи копиранията са под 2n, колкото и да е голямо n.

Идеята

Амортизирана сложност

Едно добавяне може да струва O(n): онова, което копира всичко. Но n добавяния струват общо под 3n операции: n записа и под 2n копирания. Разделено на n, това е под 3 на добавяне: O(1).

Цената, разпределена по цяла поредица от операции, се казва амортизирана сложност. Добавянето в края на списък е O(1) амортизирано.

Това не е „средно при случаен вход“. Обещанието важи за всяка поредица добавяния, без късмет: скъпите са рядко и винаги толкова рядко.

Пробвай

Предвиди изхода

Пет поръчки в масив, който започва с едно място и се удвоява. Колко копирания?

class OrderList
{
    private int[] items = new int[1];
    private int size = 0;
    public long Copies { get; private set; }


    public void Add(int order)
    {
        if (size == items.Length)
        {
            int[] bigger = new int[items.Length * 2];
            for (int i = 0; i < size; i++)
            {
                bigger[i] = items[i];
                Copies++;
            }
            items = bigger;
        }
        items[size] = order;
        size++;
    }
}


foreach (int n in new[] { 5 })
{
    var orders = new OrderList();
    for (int i = 0; i < n; i++)
    {
        orders.Add(100000 + i);
    }
    Console.WriteLine(n + " поръчки: " + orders.Copies + " копирания");
}
Отговор

Виж го

С едно място повече: O(n²)

Същият клас, само че новият масив е с едно място повече:

int[] bigger = new int[items.Length + 1];
foreach (int n in new[] { 9, 1000 })
{
    var orders = new OrderList();
    for (int i = 0; i < n; i++)
    {
        orders.Add(100000 + i);
    }
    Console.WriteLine(n + " поръчки: " + orders.Copies + " копирания");
}
Изход
9 поръчки: 36 копирания
1000 поръчки: 499500 копирания

При 1000 поръчки удвояването копира 1023 пъти, а растежът с едно място 499 500 пъти: 1 + 2 + … + 999. Пусни двата растежа и виж кривите. Броим само копиранията:

  • Растеж ×2: копирания O(n)
  • Растеж +1: копирания O(n²)
Алгоритъмn = 10n = 1000n = 100 000
Растеж ×2: копирания151023131 071
Растеж +1: копирания45499 500≈ 4 995 000 000
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

Удвояването расте като права: O(n) общо, O(1) на добавяне. Растежът с едно място расте като парабола: O(n²) общо, O(n) на добавяне.

Пробвай

Попълни

Колко места има новият масив, за да е добавянето O(1) амортизирано?

if (size == items.Length)
{
    int[] bigger = new int[];

Пробвай

Намери грешката

Колега е сменил удвояването, „за да не хаби памет“. На 1000 поръчки тестът минава бързо, а нощният внос на 100 000 се влачи:

foreach (int n in new[] { 1000, 100000 })
{
    var orders = new OrderList();
    for (int i = 0; i < n; i++)
    {
        orders.Add(100000 + i);
    }
    Console.WriteLine(n + " поръчки: " + orders.Copies + " копирания");
}
Изход
1000 поръчки: 4510 копирания
100000 поръчки: 49951000 копирания

При 100 пъти повече поръчки копиранията са 10 000 пъти повече. На кой ред е грешката?

Избери реда с грешката.

Идеята

Как расте всеки език

Нито един език не удвоява точно, но всеки умножава:

  • Java ArrayList: ×1,5;
  • C# List<T>: ×2. Празният получава 4 места при първото Add, а колко места има, казва Capacity.
  • Python (CPython): около ×1,125;
  • JavaScript (V8): около ×1,5.

Всеки множител над 1 дава O(1) амортизирано. Колкото е по-малък, толкова повече копирания (при ×1,5 са под 3n, при ×1,125 под 9n) и толкова по-малко празни места след растене. Изборът е размяна между време и памет, както в урока „Сложност по памет“.

Колко места има списъкът при всяко растене, за 1000 добавяния:

var orders = new List<int>();
var seen = new List<int>();
for (int i = 0; i < 1000; i++)
{
    orders.Add(100000 + i);
    if (seen.Count == 0 || seen[^1] != orders.Capacity)
    {
        seen.Add(orders.Capacity);
    }
}
Console.WriteLine("Местата при всяко растене: " + string.Join(" ", seen));
Изход
Местата при всяко растене: 4 8 16 32 64 128 256 512 1024
По-точно, за любопитните

O(1) амортизирано не значи, че всяко добавяне е бързо. Добавянето, което копира, е O(n). В повечето програми това не се усеща, но в програма, която не бива да спира (каса, игра, обработка на звук), едно добавяне на милионния елемент може да е бавното. Ако знаеш колко ще са елементите, задай местата отначало: new List<int>(n). Тогава списъкът не копира никога.

List<T> има и EnsureCapacity(n) за списък, който вече съществува.

Сметката за ×2 има и друг вид: всяко добавяне „плаща“ 2 копирания напред и ги спестява. Когато масивът с k елемента се напълни, последните k/2 добавяния са спестили k, точно колкото струва копирането. Спестеното никога не става отрицателно, затова сборът е под 2n.

Упражнение

Растеж като в Java

Реши задачата в редактора си.

Растеж с половината. Смени растежа на OrderList така, че новият масив да има старите места плюс половината (поне едно място повече). Преброй копиранията при 1000 и при 100 000 поръчки. Под 2n ли са? А под 3n?

Изход
1000 поръчки: 2137 копирания, 2n = 2000
100000 поръчки: 276521 копирания, 2n = 200000

Още задачи

  • Махане от края. Добави removeLast. Кога масивът да се свива, така че махането също да е O(1) амортизирано? Пробвай „наполовина, когато е пълен до половината“ и редувай добавяне и махане точно на границата. После пробвай „наполовина, когато е пълен до една четвърт“. Защо второто е O(1) амортизирано, а първото не?
  • Колко места хаби. След 1000 добавяния с удвояване колко от местата са празни? А с растеж ×1,5?

Тест

Провери се

1. Масив се удвоява, когато се напълни. Колко копирания правят общо 1000 добавяния, ако започва с 1 място?
2. Какво значи „добавянето е O(1) амортизирано“?
3. Колега сменя растежа от ×2 на +1000 места, „за да не хаби памет“. Какво става при милион добавяния?
4. Защо Java расте ×1,5, а не ×2 или ×10?
5. Програма за касата не бива да спира за повече от милисекунда на добавяне. Какво правиш?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·