Разделяй и владей и дървото на рекурсията в Java

Проблем

Колко доставки са разменени

Куриерската фирма обещава на всеки клиент час за доставка. Така поръчките имат обещан ред: 1, 2, 3 и така нататък. Колите обаче карат както карат, и вечерта отчетът пита: колко далеч е днешният ред на доставките от обещания?

Мярката е броят на разменените двойки: поръчка 5 е доставена преди поръчка 3, макар че 3 е обещана по-рано. Такава двойка се казва инверсия. Ако доставките са точно по обещания ред, инверсиите са 0.

Първото решение проверява всяка двойка:

static long countPairs(int[] ranks) {
    long inversions = 0;
    for (int i = 0; i < ranks.length; i++) {
        for (int j = i + 1; j < ranks.length; j++) {
            if (ranks[i] > ranks[j]) {
                inversions++;
            }
        }
    }
    return inversions;
}

int[] ranks = {4, 1, 7, 3, 8, 2, 6, 5};
System.out.println("Инверсии: " + countPairs(ranks));

Инверсии: 12

За 8 поръчки това са 28 двойки. За n поръчки са n(n − 1)/2, тоест O(n²). Фирмата прави 100 000 доставки на ден, а двойките са 4 999 950 000. Отчетът, който на теста е миг, вечер върви с минути.

Идеята

Раздели, преброй, сглоби

Подходът е разделяй и владей, като в merge sort: раздели доставките на първата и втората половина. Всяка разменена двойка е от един от три вида:

и двете поръчки са в първата половина;
и двете са във втората;
едната е в първата, другата във втората.

Първите два вида са същата задача, само че наполовина по-малка: рекурсията ги брои. Трудното е третият вид, двойките между половините. Ако проверяваш всяка, пак си на n².

Тук помага сливането. Нека двете половини вече са подредени. При сливане взимаш по-малкото от двете първи невзети числа. Когато по-малкото е отдясно, всяко невзето отляво е по-голямо от него, а е дошло по-рано, защото е от първата половина. Всяко от тях е една инверсия. Затова едно сравнение брои наведнъж колкото са невзетите отляво.

Така броенето „се качва“ на merge sort: същото делене, същото сливане и един ред повече.

Виж го

Броене при сливането

sortCount подрежда доставките на място и връща колко инверсии има в тях. Гледай последното сливане: всяко число отдясно, което слиза, брои невзетите отляво:

static long sortCount(int[] ranks) {
    int n = ranks.length;
    if (n <= 1) {
        return 0;
    }
    int mid = n / 2;
    int[] left = Arrays.copyOfRange(ranks, 0, mid);
    int[] right = Arrays.copyOfRange(ranks, mid, n);
    long a = sortCount(left);
    long b = sortCount(right);
    long cross = 0;
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            ranks[k++] = left[i++];
        } else {
            cross += left.length - i;
            ranks[k++] = right[j++];
        }
    }
    while (i < left.length) {
        ranks[k++] = left[i++];
    }
    while (j < right.length) {
        ranks[k++] = right[j++];
    }
    return a + b + cross;
}

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

sortCount получава 8 поръчки в реда, в който са дошли. Числото е мястото на поръчката в обещания ред.
mid = 4: първите четири доставки [4, 1, 7, 3] и последните четири [8, 2, 6, 5]. Всяка разменена двойка е или вътре в половина, или между двете.
Всяка половина вика sortCount за себе си: брои своите двойки (a = 3, b = 4) и се връща подредена.
Сега двойките между половините. i и j сочат първото невзето число. 1 < 2: лявото слиза, без инверсия.
2 отдясно е по-малко. Всяко невзето отляво ([3, 4, 7]) е по-голямо и е дошло по-рано: left.length - i = 3 инверсии наведнъж.
Същото правило всеки път: 5 добавя 1, 6 добавя 1. cross = 5, след 7 сравнения.
Едната страна свърши. Остатъкът отива накрая без сравнение: той не добавя инверсии.
a + b + cross = 3 + 4 + 5 = 12. Проверката по двойки гледа всички 28 двойки; сливането намира същите 12 с общо 17 сравнения.

int[] ranks = {4, 1, 7, 3, 8, 2, 6, 5};
System.out.println("Инверсии: " + sortCount(ranks));
System.out.println("Подредени: " + Arrays.toString(ranks));

Инверсии: 12
Подредени: [1, 2, 3, 4, 5, 6, 7, 8]

Функцията подрежда масива, който получава. Ако ти трябва и редът на доставките, подай копие.

В Java няма как функция да върне два резултата без нов клас, затова sortCount връща броя, а подреждането става в самия масив. Ако искаш и двете отделно, record Counted(int[] sorted, long count) е кратък начин.

Пробвай

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

Двете половини, [2, 4, 6] и [1, 3, 5], вече са подредени, затова вътре в тях инверсии няма. Колко има между тях?

static long sortCount(int[] ranks) {
    int n = ranks.length;
    if (n <= 1) {
        return 0;
    }
    int mid = n / 2;
    int[] left = Arrays.copyOfRange(ranks, 0, mid);
    int[] right = Arrays.copyOfRange(ranks, mid, n);
    long a = sortCount(left);
    long b = sortCount(right);
    long cross = 0;
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            ranks[k++] = left[i++];
        } else {
            cross += left.length - i;
            ranks[k++] = right[j++];
        }
    }
    while (i < left.length) {
        ranks[k++] = left[i++];
    }
    while (j < right.length) {
        ranks[k++] = right[j++];
    }
    return a + b + cross;
}

int[] ranks = {2, 4, 6, 1, 3, 5};
System.out.println("Инверсии: " + sortCount(ranks));

Отговор

Инверсии: 3

Инверсии: 15

Инверсии: 6

Идеята

Дървото на рекурсията

Колко струва това? Нарисувай извикванията като дърво. Най-горе е извикването с всичките n поръчки. Под него са двете, които то прави, с по n/2. Под всяко от тях още две, и така до дъното.

После за всяко извикване отбележи работата му: какво прави то само, извън своите рекурсивни извиквания. Тук това е сливането: то минава всяка поръчка, която извикването е получило, веднъж.

Сега събери по нива. Най-горе работата е n. На следващото ниво са две извиквания по n/2: пак n. После четири по n/4: пак n. Нивата са колко пъти n се дели на две до 1, около log₂ n. Значи цената е нивата по работата на ниво: n · log₂ n.

Това се казва дърво на рекурсията. То е начинът да преброиш цената на всяко „разделяй и владей“: не гадаеш, а събираш ниво по ниво.

Виж го

Три дървета, три цени

Същото броене за три функции на 8 поръчки. Двоичното търсене от урока за него, написано с рекурсия. Броенето чрез сливане. И трета функция, която също дели, но лошо: първите n − 1 поръчки рекурсивно, а последната сравнява с всички преди нея.

static long sortCount(int[] ranks) {
    int n = ranks.length;
    if (n <= 1) {
        return 0;
    }
    int mid = n / 2;
    int[] left = Arrays.copyOfRange(ranks, 0, mid);
    int[] right = Arrays.copyOfRange(ranks, mid, n);
    long a = sortCount(left);
    long b = sortCount(right);
    long cross = 0;
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            ranks[k++] = left[i++];
        } else {
            cross += left.length - i;
            ranks[k++] = right[j++];
        }
    }
    while (i < left.length) {
        ranks[k++] = left[i++];
    }
    while (j < right.length) {
        ranks[k++] = right[j++];
    }
    return a + b + cross;
}

static int find(int[] ranks, int target, int lo, int hi) {
    if (lo > hi) {
        return -1;
    }
    int mid = (lo + hi) / 2;
    if (ranks[mid] == target) {
        return mid;
    }
    if (ranks[mid] < target) {
        return find(ranks, target, mid + 1, hi);
    }
    return find(ranks, target, lo, mid - 1);
}

static long countSlow(int[] ranks, int n) {
    if (n <= 1) {
        return 0;
    }
    long inv = countSlow(ranks, n - 1);
    for (int i = 0; i < n - 1; i++) {
        if (ranks[i] > ranks[n - 1]) {
            inv++;
        }
    }
    return inv;
}

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

Всяка кутия е едно извикване, а числото в нея е колко поръчки получава. find поглежда средата веднъж: работа 1.
После вика себе си за ЕДНАТА половина: 8 → 4 → 2 → 1. Един клон, и всяко ниво прави 1.
4 нива × 1 = 4. Нивата са колко пъти n се дели на две до 1, около log₂ n: O(log n).
sortCount вика себе си за ДВЕТЕ половини. Сливането най-горе минава всичките 8 поръчки, двете под него 4 + 4 = 8.
На всяко ниво извикванията са два пъти повече, а поръчките на всяко са наполовина: работата на ниво остава 8. Извикванията с една поръчка само се връщат: 0.
3 нива × 8 = 24: log₂ n нива по n, O(n log n). При 100 000 поръчки това са 17 нива, не 100 000.
countSlow също дели, но лошо: първите n − 1 поръчки и последната. Рекурсията продължава с n − 1: 8 → 7 → 6 …
На всяко ниво последната поръчка се сравнява с всички преди нея: 7, 6, … 1. 8 нива, и 7 + 6 + 5 + … + 1 = 28: точно 28-те двойки, O(n²).
Цената е формата на дървото: нивата по работата на ниво. Деленето наполовина дава log n нива, отделянето по едно дава n нива. Не стига да делиш: половините трябва да са равни.

int[] sorted = {1, 2, 3, 4, 5, 6, 7, 8};
System.out.println("find: " + find(sorted, 8, 0, sorted.length - 1));
int[] ranks = {4, 1, 7, 3, 8, 2, 6, 5};
System.out.println("countSlow: " + countSlow(ranks, ranks.length));
System.out.println("sortCount: " + sortCount(ranks));

find: 7
countSlow: 12
sortCount: 12

Формата на дървото решава:

Един клон, половината: log₂ n нива по малко работа. O(log n).
Два клона, половините: log₂ n нива по n. O(n log n).
Един клон, едно по-малко: n нива по n. O(n²). Това е проверката по двойки, само че написана с рекурсия.

Същото става в quick sort с лош пивот: при подреден вход пивотът отделя една цена, а другите n − 1 остават в една част. Дървото е верига от n нива, и сложността е n².

Виж го

Измери го: по двойки срещу чрез сливане

Пусни двете върху едни и същи доставки. При двойките броим проверените двойки, при сливането сравненията. По двойки при 100 000 не се пуска наистина: Bench го оценява по кривата.

Инверсии по двойки O(n²)
Инверсии чрез сливане O(n log n)

Алгоритъм	n = 10	n = 1000	n = 10 000	n = 100 000
Инверсии по двойки	45	499 500	49 995 000	≈ 4 999 500 000
Инверсии чрез сливане	21	8693	120 553	1 536 329

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

static long sortCount(int[] ranks) {
    int n = ranks.length;
    if (n <= 1) {
        return 0;
    }
    int mid = n / 2;
    int[] left = Arrays.copyOfRange(ranks, 0, mid);
    int[] right = Arrays.copyOfRange(ranks, mid, n);
    long a = sortCount(left);
    long b = sortCount(right);
    long cross = 0;
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            ranks[k++] = left[i++];
        } else {
            cross += left.length - i;
            ranks[k++] = right[j++];
        }
    }
    while (i < left.length) {
        ranks[k++] = left[i++];
    }
    while (j < right.length) {
        ranks[k++] = right[j++];
    }
    return a + b + cross;
}

При 1000 доставки двойките са 499 500, а сравненията 8693. При 100 000 сливането прави 1 536 329 сравнения срещу 4 999 950 000 двойки: над 3000 пъти по-малко. А инверсиите са същите, 2 504 458 463.

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

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

static long checks = 0;
static long comparisons = 0;

static int[] deliveries(int n) {
    int[] ranks = new int[n];
    for (int k = 0; k < n; k++) {
        ranks[k] = k + 1;
    }
    long x = 2026;
    for (int k = n - 1; k > 0; k--) {
        x = x * 48271 % 2147483647;
        int j = (int) (x % (k + 1));
        int t = ranks[k];
        ranks[k] = ranks[j];
        ranks[j] = t;
    }
    return ranks;
}

static long countPairs(int[] ranks) {
    long inversions = 0;
    for (int i = 0; i < ranks.length; i++) {
        for (int j = i + 1; j < ranks.length; j++) {
            checks++;
            if (ranks[i] > ranks[j]) {
                inversions++;
            }
        }
    }
    return inversions;
}

static long sortCount(int[] ranks) {
    int n = ranks.length;
    if (n <= 1) {
        return 0;
    }
    int mid = n / 2;
    int[] left = Arrays.copyOfRange(ranks, 0, mid);
    int[] right = Arrays.copyOfRange(ranks, mid, n);
    long a = sortCount(left);
    long b = sortCount(right);
    long cross = 0;
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        comparisons++;
        if (left[i] <= right[j]) {
            ranks[k++] = left[i++];
        } else {
            cross += left.length - i;
            ranks[k++] = right[j++];
        }
    }
    while (i < left.length) {
        ranks[k++] = left[i++];
    }
    while (j < right.length) {
        ranks[k++] = right[j++];
    }
    return a + b + cross;
}

for (int n : new int[] {10, 1000}) {
    checks = 0;
    long inv = countPairs(deliveries(n));
    System.out.println("по двойки, n = " + n + ": " + checks + " проверки, " + inv + " инверсии");
}
for (int n : new int[] {10, 1000, 100000}) {
    comparisons = 0;
    long inv = sortCount(deliveries(n));
    System.out.println("чрез сливане, n = " + n + ": " + comparisons + " сравнения, " + inv + " инверсии");
}

по двойки, n = 10: 45 проверки, 14 инверсии
по двойки, n = 1000: 499500 проверки, 249193 инверсии
чрез сливане, n = 10: 21 сравнения, 14 инверсии
чрез сливане, n = 1000: 8693 сравнения, 249193 инверсии
чрез сливане, n = 100000: 1536329 сравнения, 2504458463 инверсии

Инверсиите при 100 000 са над 2,5 милиарда, а int стига до 2 147 483 647. Затова броячите са long. С int числото щеше да прехвърли и да излезе отрицателно, без никаква грешка.

Пробвай

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

Колега е преписал функцията. За 8-те доставки от сцената тя казва 5 вместо 12:

int[] ranks = {4, 1, 7, 3, 8, 2, 6, 5};
System.out.println("Инверсии: " + sortCount(ranks));
System.out.println("Подредени: " + Arrays.toString(ranks));

Инверсии: 5
Подредени: [1, 2, 3, 4, 5, 6, 7, 8]

На кой ред е грешката?

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

Пробвай

Попълни

Дясното число е по-малко и слиза. С колко расте cross?

static long sortCount(int[] ranks) {
    int n = ranks.length;
    if (n <= 1) {
        return 0;
    }
    int mid = n / 2;
    int[] left = Arrays.copyOfRange(ranks, 0, mid);
    int[] right = Arrays.copyOfRange(ranks, mid, n);
    long a = sortCount(left);
    long b = sortCount(right);
    long cross = 0;
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            ranks[k++] = left[i++];
        } else {
            cross += ;
            ranks[k++] = right[j++];
        }
    }
    while (i < left.length) {
        ranks[k++] = left[i++];
    }
    while (j < right.length) {
        ranks[k++] = right[j++];
    }
    return a + b + cross;
}

Упражнение

Отчетът за деня

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

Разменени двойки. Прочети реда на доставките (обещаните номера, разделени с интервал) и отпечатай колко двойки са разменени и от колко общо. Ползвай sortCount от урока.

3 1 2 6 4 5 10 7 9 8

Разменени двойки: 8 от 45

Още задачи

Нарисувай дървото. Функция дели входа на три равни части и вика себе си за всяка, а работата ѝ извън извикванията е n. Нарисувай нивата: колко са и колко е работата на ниво? А ако частите са две, но работата на всяко извикване е n²?
Кои закъсняват най-много. За всяка поръчка преброй колко поръчки с по-голям номер са доставени преди нея. Сборът на тези числа е броят на инверсиите. Как да ги събереш по време на сливането? Подсказка: когато слиза число отдясно, за него се броят невзетите отляво.
Близо ли е до подредено. Преброй инверсиите в ред, който е почти подреден (две съседни поръчки разменени). Колко сравнения прави сливането? А insertion sort от простите сортирания върху същия вход?

По-точно

Мастър теоремата и другите езици

Дървото на рекурсията работи за всяко „разделяй и владей“. За най-честия вид има и готово правило.

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

Мастър теоремата, като интуиция. Функция, която дели входа на b равни части, вика себе си a пъти и прави работа f(n) извън извикванията, се описва като T(n) = a · T(n/b) + f(n). Нарисувай дървото и сравни работата горе с работата на дъното:

Работата е еднаква на всяко ниво. Умножаваш по броя нива, log n. Merge sort: T(n) = 2 · T(n/2) + n, по n на ниво, O(n log n). Двоичното търсене: T(n) = T(n/2) + 1, по 1 на ниво, O(log n).
Работата намалява надолу. Горното ниво решава. T(n) = 2 · T(n/2) + n² е O(n²): долните нива са n²/2, n²/4 и така нататък, а сборът им е под още едно n².
Работата расте надолу. Листата решават. Умножението на големи числа на Карацуба е T(n) = 3 · T(n/2) + n: три половини на всяко ниво, работата расте с 3/2 на ниво, и сложността е около n^1,58 вместо n² на училищното умножение.

Лошото делене T(n) = T(n − 1) + n изобщо не е от този вид: входът не се дели на b, а намалява с едно. Там теоремата не помага, но дървото помага: n нива по около n, O(n²).

Математиката отзад е във всеки учебник по алгоритми. За работа стига картинката: колко нива и колко работа на ниво.

Колко дълбоко отива рекурсията. Стекът от извиквания е толкова висок, колкото нивата на дървото. Броенето чрез сливане е 17 нива за 100 000 поръчки и се събира навсякъде. Лошото делене е n нива.

Java, C# и JavaScript нямат лимит в брой нива, но стекът им е около 1 MB. При 100 000 вложени извиквания и той свършва, както в quick sort с лош пивот. В Python лимитът е 1000 нива, и лошото делене пада още около 1000 поръчки.

Инверсиите като мярка. Броят инверсии между две подредби е мярка колко се различават: така се сравняват класирания, например резултатите на търсачка с оценките на хора. Insertion sort прави точно толкова размествания, колкото инверсии има входът. Затова е бърз за почти подреден вход и бавен за разбъркан.

Тест

Провери се

1. Дървото на рекурсията на една функция има log₂ n нива, а на всяко ниво работата е общо n. Колко е цената?O(log n)O(n)O(n log n)

2. Функцията вика себе си веднъж, за половината от входа, и прави постоянна работа. Колко е цената?O(n log n)O(log n)O(n)

3. Функцията дели входа на първите n − 1 и последния, вика себе си за n − 1 и сравнява последния с всички останали. Колко е цената?O(n²)O(n)O(n log n)

4. При сливането дясното число е по-малко, а отляво остават 3 невзети. Колко инверсии добавя това взимане?310

5. Защо в Java и C# броят на инверсиите е long, а не int?long е по-бърз от intЗащото сливането работи само с longПри 100 000 поръчки инверсиите могат да са около 2,5 милиарда, а int стига до около 2,1 милиарда

Разделяй и владей и дървото на рекурсията

Бисквитки