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

Времева сложност: броене на стъпки

Накратко: Времевата сложност казва как расте броят на основните операции с размера на входа: вложеният цикъл прави n(n − 1) / 2 стъпки, а едно минаване с множество прави n.

Проблем

Отчетът, който не свършва

Всеки месец онлайн магазинът пуска отчет за продажбите. Една от проверките в него търси двойни плащания: едно и също плащане, минало два пъти заради повторно натиснат бутон. Методът сравнява всяко плащане с всяко след него:

static int doublePayments(int[] ids) {
    int found = 0;
    for (int i = 0; i < ids.length; i++) {
        for (int j = i + 1; j < ids.length; j++) {
            if (ids[i] == ids[j]) {
                found++;
            }
        }
    }
    return found;
}
int[] ids = {100231, 100232, 100233, 100232, 100234};
System.out.println("Двойни плащания: " + doublePayments(ids));
Изход
Двойни плащания: 1

Преди година поръчките бяха 1 000 на месец и отчетът беше готов за 2 секунди. Днес са 100 000. Отчетът тръгва вечерта и сутринта още не е свършил. Кодът не е пипан. Данните са 100 пъти повече, а времето не е 100 пъти повече, а много повече.

Защо? И как можеше да се знае предварително, без да чакаш цяла нощ?

Идеята

Секундите лъжат, стъпките не

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

  • машината: лаптопът и сървърът дават различни числа;
  • натоварването: същият отчет е по-бавен, докато сървърът обслужва и клиентите;
  • езика: една и съща сметка е няколко пъти по-бавна на Python, отколкото на Java или C#.

Затова се мери друго: колко пъти програмата прави своята основна операция. Тук това е едно сравнение на два номера. Броят им не зависи нито от машината, нито от езика, а само от алгоритъма и от входа. Това се казва брой операции (или брой стъпки).

Броят операции не казва секундите. Казва нещо по-полезно: колко пъти повече работа идва, когато данните растат.

Виж го

Броим стъпките

Слагаш брояч до сравнението. Всяко сравнение е една стъпка:

static long steps = 0;


static int doublePayments(int[] ids) {
    int found = 0;
    for (int i = 0; i < ids.length; i++) {
        for (int j = i + 1; j < ids.length; j++) {
            steps++;
            if (ids[i] == ids[j]) {
                found++;
            }
        }
    }
    return found;
}

Отчетът се пуска върху 10, 1 000 и 2 000 плащания с различни номера:

for (int n : new int[] {10, 1000, 2000}) {
    int[] ids = new int[n];
    for (int k = 0; k < n; k++) {
        ids[k] = 100000 + k;
    }
    steps = 0;
    doublePayments(ids);
    System.out.println("n = " + n + ": " + steps + " стъпки");
}
Изход
n = 10: 45 стъпки
n = 1000: 499500 стъпки
n = 2000: 1999000 стъпки

Първото плащане се сравнява с n − 1 други, второто с n − 2 и така до последното, което няма с кого. Сборът е

n(n − 1) / 2

При 1 000 плащания това са 499 500 стъпки. При 100 000 са 4 999 950 000: 10 010 пъти повече за 100 пъти повече данни. Ако двете секунди отиваха почти изцяло за сравненията, сега отиват над пет часа и половина. Отговорът беше в кода още преди година: трябваше да преброиш.

Виж го

Защо почти ×4

static long steps = 0;


static int doublePayments(int[] ids) {
    int found = 0;
    for (int i = 0; i < ids.length; i++) {
        for (int j = i + 1; j < ids.length; j++) {
            steps++;
            if (ids[i] == ids[j]) {
                found++;
            }
        }
    }
    return found;
}
Стъпка по стъпка, с думи
  1. Четири плащания. Външният цикъл взима първото, i = 0: то ще се сравни с всяко плащане след него.
  2. j минава плащанията след i. Всяко сравнение е една стъпка и клетката на двойката светва: steps = 1, 2, 3.
  3. i се мести напред, а j тръгва пак от i + 1. Двойките са 3 + 2 + 1 = 6: триъгълник.
  4. Двойно повече плащания: 8. Стъпките не са 12, а 28.
  5. 28 = 6 стари двойки + 6 двойки от новите + 16 двойки ново със старо. Почти ×4: при 1 000 → 2 000 плащания стъпките са 499 500 → 1 999 000.
  6. Поправката минава веднъж и помни номерата в seen: 8 плащания, 8 стъпки. Тук двойно повече плащания значи двойно повече стъпки.

Удвояването не е само „още толкова плащания“. Старите 6 двойки остават. Идват 6 двойки между новите плащания. И още 16: всяко от 4-те нови с всяко от 4-те стари. Общо 28. Частта „ново със старо“ е квадрат и тя расте най-бързо. Затова при голямо n удвояването дава почти точно ×4.

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

Сметката за всяко n: при 2n плащания двойките са 2n(2n − 1) / 2 = 4 · n(n − 1) / 2 + n. Тоест четири пъти старите двойки и още n. При n = 4 това е 4 · 6 + 4 = 28, а при n = 1 000 е 4 · 499 500 + 1 000 = 1 999 000. Добавката n е малка пред останалото, и колкото по-голямо е n, толкова по-малка.

Пробвай

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

Два вложени цикъла. Първият минава 4 склада и за всеки 3 часа за доставка. Вторият минава всяка двойка от 4 склада. Какво печата програмата?

int full = 0;
for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 3; j++) {
        full++;
    }
}
int pairs = 0;
for (int i = 0; i < 4; i++) {
    for (int j = i + 1; j < 4; j++) {
        pairs++;
    }
}
System.out.println(full + " " + pairs);
Отговор

Пробвай

Попълни

Отчетът трябва да сравни всяка двойка точно веднъж и да не сравнява плащане със самото себе си. Откъде тръгва вътрешният цикъл?

static int doublePayments(int[] ids) {
    int found = 0;
    for (int i = 0; i < ids.length; i++) {
        for (int j = ; j < ids.length; j++) {
            if (ids[i] == ids[j]) {
                found++;
            }
        }
    }
    return found;
}

Виж го

Поправката: едно минаване

Не е нужно всяко плащане да се сравнява с всяко. Достатъчно е да помниш номерата, които вече си видял. Множеството (set) пази тези номера и казва дали даден номер е в него, без да ги минава един по един.

static long steps = 0;


static int doublePayments(int[] ids) {
    Set<Integer> seen = new HashSet<>();
    int found = 0;
    for (int id : ids) {
        steps++;
        if (!seen.add(id)) {
            found++;
        }
    }
    return found;
}
seen.add(id) връща false, ако номерът вече е в множеството: тогава плащането е двойно.
for (int n : new int[] {10, 1000, 2000}) {
    int[] ids = new int[n];
    for (int k = 0; k < n; k++) {
        ids[k] = 100000 + k;
    }
    steps = 0;
    doublePayments(ids);
    System.out.println("n = " + n + ": " + steps + " стъпки");
}
Изход
n = 10: 10 стъпки
n = 1000: 1000 стъпки
n = 2000: 2000 стъпки

Стъпките са колкото плащанията. Двойно повече плащания значи двойно повече стъпки. Пусни двата отчета един до друг:

  • Всяка двойка поръчки O(n²)
  • Отчетът с множество (set) O(n)
Алгоритъмn = 10n = 1000n = 2000n = 4000n = 100 000
Всяка двойка поръчки45499 5001 999 0007 998 000≈ 4 998 750 000
Отчетът с множество (set)10100020004000100 000
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
По-точно, за любопитните

Коя е основната операция? Тази, която се повтаря най-много и от която зависи времето. В бавния отчет това е сравнението във вътрешния цикъл. Увеличаването на i и j и проверката дали цикълът е свършил също се повтарят, но колкото сравненията, не повече. Затова броят им не сменя картината и не се брои отделно.

Проверката в множеството една стъпка ли е? Не съвсем: зад множеството стои hash таблица, която смята hash на номера и гледа в една кофа. Средно това е една и съща малка работа, колкото и номера да има вътре. Как става, ще видиш в модула „Структури от данни“. Тук я броим за една стъпка, както я брои и Bench.

Секундите на различните езици. Броят стъпки е еднакъв, а времето не е. Java компилира горещия цикъл до машинен код по време на работа (JIT), затова първите хиляди стъпки са по-бавни от следващите. HashSet<Integer> пази обекти Integer, а не int, и всеки номер се опакова (boxing). Това струва малко повече на стъпка, но не сменя броя им.

Упражнение

Продажбите по продукт

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

Колко стъпки. Отчетът за продажбите брои колко пъти е поръчан всеки от 50-те продукта. Поръчката е номерът на продукта (от 0 до 49):

static int[] salesByProduct(int[] orders, int products) {
    int[] sales = new int[products];
    for (int p = 0; p < products; p++) {
        for (int product : orders) {
            if (product == p) {
                sales[p]++;
            }
        }
    }
    return sales;
}

Добави брояч steps пред сравнението. Пусни метода с 1 000 и с 2 000 поръчки, в които продуктът на поръчка k е k % 50, и изпечатай стъпките:

Изход
n = 1000: 50000 стъпки
n = 2000: 100000 стъпки

Цикълът е вложен, а стъпките растат само двойно. Защо?

Още задачи

  • Едно минаване. Направи отчета за продажбите с едно минаване по поръчките: sales[product] расте с едно за всяка поръчка. Колко стъпки са при 1 000 поръчки?
  • Отчетът на годината. Колко стъпки прави бавният отчет за двойни плащания за цяла година с по 100 000 плащания на месец? Сметни с n(n − 1) / 2, без да го пускаш.
  • Твоят код. Намери в свой код вложен цикъл и преброй стъпките за два размера на входа. Какво става, когато входът се удвои?

Тест

Провери се

1. Защо броим операции, а не секунди?
2. Отчетът сравнява всяко плащане с всяко след него. Плащанията стават двойно повече. Колко пъти повече са стъпките?
3. Отчетът за продажбите минава всичките 50 продукта, а за всеки продукт минава всички поръчки. Поръчките стават двойно повече. Колко пъти повече са стъпките?
4. Колко стъпки прави поправката с множеството при 100 000 плащания?

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