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

Код на:JavaC#PythonJavaScript

Накратко: Амортизираната сложност е средната цена на операция в дълга поредица: добавянето в динамичен масив понякога копира всичко, но щом масивът расте с множител (например ×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;
        orders = Arrays.copyOf(orders, orders.length + 1);
        orders[orders.length - 1] = 100000 + i;
    }
    return copies;
}

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

for (int n : new int[] {1000, 10000}) {
    System.out.println(n + " поръчки: " + importOrders(n) + " копирания");
}

Изход

1000 поръчки: 499500 копирания
10000 поръчки: 49995000 копирания

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

Идеята

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

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

ArrayList<String> cart = new ArrayList<>(3);
cart.add("Хляб");
cart.add("Мляко");
cart.add("Кафе");
cart.add("Масло");
cart.remove("Мляко");
System.out.println(cart);
System.out.println("Продукти: " + cart.size());

Стъпка по стъпка, с думи

1. cart сочи обект ArrayList. Вътре има масив с 3 места и брояч size.
2. add слага всеки елемент на първото свободно място и увеличава size.
3. Масивът е пълен. ArrayList прави нов с 4 места и копира трите елемента в него.
4. Обектът вече сочи новия масив, а старият не трябва на никого. „Масло“ влиза на свободното място.
5. remove маха „Мляко“, а всичко след него се мести с едно място наляво. Дупка не остава.
6. Отвън се вижда само списък с три продукта: копирането и местенето ги прави ArrayList.

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

Виж го

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

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

class OrderList {
    private int[] items = new int[1];
    private int size = 0;
    long copies = 0;

    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++;
    }
}

for (int n : new int[] {9, 1000}) {
    OrderList orders = new OrderList();
    for (int i = 0; i < n; i++) {
        orders.add(100000 + i);
    }
    System.out.println(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;
    long copies = 0;

    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++;
    }
}

OrderList 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;
    long copies = 0;

    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++;
    }
}

for (int n : new int[] {5}) {
    OrderList orders = new OrderList();
    for (int i = 0; i < n; i++) {
        orders.add(100000 + i);
    }
    System.out.println(n + " поръчки: " + orders.copies + " копирания");
}

Отговор

5 поръчки: 10 копирания

5 поръчки: 4 копирания

5 поръчки: 7 копирания

Провери

Виж го

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

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

int[] bigger = new int[items.length + 1];

for (int n : new int[] {9, 1000}) {
    OrderList orders = new OrderList();
    for (int i = 0; i < n; i++) {
        orders.add(100000 + i);
    }
    System.out.println(n + " поръчки: " + orders.copies + " копирания");
}

Изход

9 поръчки: 36 копирания
1000 поръчки: 499500 копирания

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

• Растеж ×2: копирания O(n)
• Растеж +1: копирания O(n²)

Алгоритъм	n = 10	n = 1000	n = 100 000
Растеж ×2: копирания	15	1023	131 071
Растеж +1: копирания	45	499 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 се влачи:

for (int n : new int[] {1000, 100000}) {
    OrderList orders = new OrderList();
    for (int i = 0; i < n; i++) {
        orders.add(100000 + i);
    }
    System.out.println(n + " поръчки: " + orders.copies + " копирания");
}

Изход

1000 поръчки: 4510 копирания
100000 поръчки: 49951000 копирания

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

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

1class OrderList {2 private int[] items = new int[1];3 private int size = 0;4 long copies = 0;56 void add(int order) {7 if (size == items.length) {8 int[] bigger = new int[items.length + 100];9 for (int i = 0; i < size; i++) {10 bigger[i] = items[i];11 copies++;12 }13 items = bigger;14 }15 items[size] = order;16 size++;17 }18}

Провери

Идеята

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

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

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

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

По-точно, за любопитните

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

ArrayList има и 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 място?

Точно 1000Под 20001000 × 1000

2. Какво значи „добавянето е O(1) амортизирано“?

n добавяния струват общо O(n), макар че някое от тях копира всичкоДобавянето е бързо средно за случаен входВсяко добавяне е бързо

3. Колега сменя растежа от ×2 на +1000 места, „за да не хаби памет“. Какво става при милион добавяния?

Нищо, 1000 е много местаСтава по-бързо, защото масивът е по-малъкКопиранията стават около n²/2000: половин милиард вместо около милион

4. Защо Java расте ×1,5, а не ×2 или ×10?

Колкото по-голям е множителят, толкова по-малко копирания, но толкова повече празни места след растенеСамо ×1,5 дава O(1) амортизираноЗащото ×1,5 е по-бързо за процесора

5. Програма за касата не бива да спира за повече от милисекунда на добавяне. Какво правиш?

Сменяш на растеж +1Задаваш местата отначало, ако знаеш колко ще са елементитеНищо, добавянето е O(1)

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Времева сложност: броене на стъпки · Big-O: как расте работата · Най-добър, среден и най-лош случай · Сложност по памет
• Продължава в: Динамичен масив отвътре · Свързан списък · Стек и опашка · Хеш таблица
• Задачи по темата: Сложност