Розв'язки до вправ з "An Introduction to the Analysis of Algorithms" Роберта Седжвіка. Розділ I.

Вправа 1.2

void MergeSort(std::vector<int>& a, int lo, int hi, std::vector<int>& space) {
    if (hi == lo + 1) return;
    int mid = (hi + lo) / 2;
    MergeSort(a, lo, mid, space);
    MergeSort(a, mid, hi, space);
    std::copy(a.cbegin() + lo, a.cbegin() + mid, space.begin() + lo);
    std::copy(a.cbegin() + mid, a.cbegin() + hi, space.begin() + mid);
    int left = lo;
    int right = mid;
    for (int i = lo; i < hi; ++i) {
        if (space[left] < space[right]) {
            a[i] = space[left++];
            if (left == mid) {
                std::copy(space.cbegin() + right, space.cbegin() + hi, a.begin() + i + 1);
                break;
            }
        }
        else {
            a[i] = space[right++];
            if (right == hi) {
                std::copy(space.cbegin() + left, space.cbegin() + mid, a.begin() + i + 1);
                break;
            }
        }
    }
}

Вправа 1.4

Зауважимо одразу, що $C_1 = 0, C_2 = 2$. $$\begin{align*} C_{N+1} - C_N &= C_{\lceil \frac{N+1}{2}\rceil} + C_{\lfloor \frac{N+1}{2}\rfloor} + N + 1 - \left(C_{\lceil\frac{N}{2}\rceil} + C_{\lfloor\frac{N}{2}\rfloor} + N\right)\\ &=C_{\lceil \frac{N+1}{2}\rceil} - C_{\lfloor \frac{N}{2}\rfloor} + 1\\ &=\lfloor\lg N\rfloor + 2 \end{align*}$$ Тут $\lfloor\lg N\rfloor$ - це сума одиничок. Вона дорівнює кількості разів, що ми маємо поділити $N$ на $2$ із взяттям найближчого меншого цілого, тобто ось за такою формулою: $$\left\lfloor\begin{array}{@{} c @{}} \frac{ \substack{ \left\lfloor\begin{array}{@{} c @{}} \frac{ \left\lfloor\begin{array}{@{} c @{}}\frac{\lfloor \frac{N}{2}\rfloor}{2}\end{array}\right\rfloor }{2} \end{array}\right\rfloor \\ \\ \\ \dots } }{2} \end{array}\right\rfloor = 1.$$ Навіть якщо припустити, що ми відкидаємо $0.5$ після кожного ділення, то зворотній процес виглядає так: $$(\cdots(((1\cdot 2+1)\cdot2+1)\cdot2+1)\cdots) = 2^m + 2^{m-1} + \dots < 2^{m+1}$$ Отже, $\lfloor\lg N\rfloor = m$. $2$ з'являється із $(C_2 - C_1)$ - остання ітерація. Тепер ми можемо записати $C_{N}$ як телескопічний ряд: $$\begin{equation*} C_{N} = \sum_{k=1}^{N-1} \left(C_{k+1} - C_k\right) = \sum_{k=1}^{N-1}(\lfloor\lg k\rfloor + 2). \end{equation*}$$

Вправа 1.5

Перевіримо нерівність для $N = 1$: $$C_1 = 1\cdot\lceil \lg 1\rceil + 1 - 2^{\lceil \lg 1\rceil} = 0.$$ Тепер перевіримо, що якщо нерівність виконується для $N$, то вона виконується і для $N+1$. Тут у нас є два випадки:

1. $\lceil \lg (N)\rceil = \lceil \lg (N+1)\rceil$, тобто $N \ne 2^n$. Тоді, $$\begin{align*} C_{N+1} &= (N + 1)\cdot\lceil \lg (N + 1)\rceil + N + 1 - 2^{\lceil \lg (N + 1)\rceil}\\ &= N\cdot\lceil \lg N\rceil + \lceil \lg N\rceil + N + 1 - 2^{\lceil \lg N\rceil}\\ &= C_N + \lceil \lg N\rceil + 1\\ \end{align*}$$ Тут $\lceil \lg N\rceil + 1 = \lfloor \lg N\rfloor + 2$ і використовуючи результат вправи 1.4 рівність доведена.
2. $N = 2^n$, $$\begin{align*} C_{N+1} &= (N + 1)\cdot\lceil \lg (N + 1)\rceil + N + 1 - 2^{\lceil \lg (N + 1)\rceil}\\ &= (N + 1)\cdot (\lg N + 1) + N + 1 - 2\cdot N\\ &= C_N + \lg N + 2\\ \end{align*}$$ Знов-таки, використовуючи вправу 1.4 завершуємо доведення.

Вправа 1.7

Розглянемо варіант зі складністю $N\lg N$: $$\begin{align*} t_{2N} &= 2 t_N \left(1 + 1 / \lg N\right)\\ &=2N(\lg N + 1)\\ &=2N\lg (2N). \end{align*}$$

Вправа 1.8

void merge_sort_internal(
    const vector<unsigned>::iterator a_beg,
    const vector<unsigned>::iterator a_end,
    const vector<unsigned>::iterator b_beg,
    const vector<unsigned>::iterator b_end
) {
    assert(distance(a_beg, a_end) == distance(b_beg, b_end));
    const auto dist = distance(a_beg, a_end);
    if (dist <= 1) return;
    const auto a_mid = a_beg + (dist + 1) / 2;
    const auto b_mid = b_beg + (dist + 1) / 2;
    merge_sort_internal(a_beg, a_mid, b_beg, b_mid);
    merge_sort_internal(a_mid, a_end, b_mid, b_end);
    copy(a_beg, a_end, b_beg);
    auto a = a_beg;
    auto b1 = b_beg;
    auto b2 = b_mid;
    while (b1 < b_mid && b2 < b_end) {
        *a++ = *b1 < *b2 ? *b1++ : *b2++;
    }
    copy(b1, b_mid, a);
    copy(b2, b_end, a);
}

void merge_sort(vector<unsigned>& data) {
    vector<unsigned> buffer(data.size());
    merge_sort_internal(data.begin(), data.end(), buffer.begin(), buffer.end());
}

long long test(size_t size) {
    random_device rnd_device;
    minstd_rand lce(rnd_device());
    uniform_int_distribution<unsigned> dist(1, numeric_limits<unsigned>::max());
    vector<unsigned> v(size);
    generate(v.begin(), v.end(), [&dist, &lce]() { return dist(lce); });
    auto start = chrono::system_clock::now();
    merge_sort(v);
    auto end = chrono::system_clock::now();
    auto elapsed = chrono::duration_cast<chrono::microseconds>(end - start);
    return elapsed.count();
}

int main() {
    long long t_10_6 = test(1000 * 1000);
    long long t_10_7 = test(10 * 1000 * 1000);
    long long t_10_8 = test(100 * 1000 * 1000);
    double ratio = 10. * (1. + 1. / log2(10));
    cout << t_10_6 << ", " << t_10_7 << ", " << t_10_8 << endl;
    cout << "expected ratio:" << ratio << endl;
    cout << "actual ratio 10^7 to 10^6:" << t_10_7 / static_cast<double>(t_10_6) << endl;
    cout << "actual ratio 10^8 to 10^7:" << t_10_8 / static_cast<double>(t_10_7) << endl;
    system("pause");
    return 0;
}

161000, 1776000, 20196000
expected ratio:13.0103
actual ratio 10^7 to 10^6:11.0311
actual ratio 10^8 to 10^7:11.3716

Вправи 1.9, 1.10

Використайте сортування підрахунком.

Вправи 1.11

Тут можна використати той самий підхід, що й у теоремі 1.3. $(N-1)! -$ це кількість можливих перестановок елементів для кожного розбиття. $(N+1) -$ кількість порівнянь. $$C'_N = \sum_{i=1}^N\left(C'_{i-1}+C'_{N-i}\right)+(N-1)!(N+1)$$

Вправи 1.12

Вибираючи елементи в праву і ліві частині розбиття ми порівнюємо елементи лише з опірним елементом $v$ і ніколи між собою. Через ми ніяк не впорядковуємо елементи в кожній з частин. Якщо замість j = hi; ми напишемо j = hi + 1;, то першим же обміном в циклі while (true) ми перенесемо елемент $v$ в ліву частину розбиття, і всі елементи перед ним менші ніж цей елемент. Наприклад, $$3,5,2,11,7,10,12,9$$ розбиваємо на $$3,5,2,9,7,10\quad\mbox{і}\quad12$$ і в лівій частині ми бачимо, що до першої $9$ всі елементи менше ніж $9$.

Вправа 1.13

Під час розбиття ми не робимо порівнянь між елементами лівого і правого підмасивів, таким чином ніяк не впорядковоючи їх, тому ці підмасиви також випадкові перестановки. Якщо ж ми ініціалізуємо правий вказівник j = hi + 1, то умова while (v < a[--j]) завжди хиба на першій ітерації зовнішнього циклу. Через це ми точно знаємо, що до елемента зі значенням $v$ всі елементи менші ніж він, а за ним вже можуть бути й більші. Тобто перестановка невипадкова. $$1,3,9,5,7,2,4$$ $$1,3,4,5,7,2\quad9$$ Тут $v = 4$, зауважте, що ліворуч всі елементи до $4$ менші ніж $4$.

Вправа 1.14

$$\begin{align*} A_N N &= N + 2\sum_{1\le j\le N} A_{j-1}\\ A_{N-1}(N-1) &= N-1 + 2\sum_{1\le j\le N-1} A_{j-1}. \end{align*}$$ Віднімемо друге рівняння від першого. $$\begin{align*} A_N N - A_{N-1}(N-1) &= 1 + 2A_{N-1}\\ A_N N - A_{N-1}(N+1) &= 1 \end{align*}$$ Розділемо на $N(N+1)$. $$\begin{align*} \frac{A_N}{N+1} - \frac{A_{N-1}}{N} = \frac{1}{N(N+1)} \end{align*}$$ Тепер двічі використаємо прийом телескопічного ряду. $$\begin{align*} \frac{A_N}{N+1} - \frac{A_0}{1} &= \sum_1^N\frac{1}{k(k+1)}\\ \frac{A_N}{N+1} - \frac{A_0}{1} &= \sum_1^N\left(\frac{1}{k}-\frac{1}{k+1}\right)\\ \frac{A_N}{N+1} - \frac{A_0}{1} &= \frac{1}{1}-\frac{1}{N+1}\\ \end{align*}$$ Якщо $A_0 = 0$, то $$\begin{equation*} A_N = N \end{equation*}$$ Дуже цікавий результат, і його нескладно перевірити.

Вправа 1.15

Нас цікавить скільки обмінів відбулось в тілі цього циклу:

while (true)
{
    while (a[++i] < v) ;
    while (v < a[--j]) if (j == lo) break;
    if (i >= j) break;
    t = a[i]; a[i] = a[j]; a[j] = t;
}

Фактично нам потрібно знайти математичне сподівання кількості обмінів. На останню позицію в масиві рівноймовірно може потрапити будь-який елемент. Позначимо його позицію в відсортованому масиві через $p$, а сам елемент через $v$. Отже, у нас є $N-p$ елементів більше ніж $v$ і $p-1$ елементів менше ніж $v$. Імовірність натрапити на елемент менший ніж $v$ становить $\frac{p-1}{N}$ і більший - $\frac{N-p}{N}$. Відповідно, щоб зустріти елемент більший ніж $v$ ми в середньому пройдемо $\frac{N}{N-p}$, а менший - $\frac{N}{p-1}$. В цьому циклі ми маємо зробити $N$ порівнянь, останній елемент порівнюється двічі. Отже, $$\begin{align*} \frac{1}{N}\sum_{p=1}^N\frac{N}{\frac{N}{N-p}+\frac{N}{p-1}} &= \sum_{p=1}^N\frac{1}{\frac{N(N-1)}{(N-p)(p-1)}}\\ &=\frac{1}{N(N-1)}\sum_{p=1}^N(Np - N - P^2 +p)\\ &=\frac{1}{N-1}\left(-N + \frac{N(N+1)}{2} - \frac{1}{N}\sum_{p=1}^N p^2 + \frac{N+1}{2}\right)\\ &=\frac{1}{N-1}\left(-N + \frac{N(N+1)}{2} - \frac{(N+1)(2N+1)}{6} + \frac{N+1}{2}\right)\\ &=\frac{1}{N-1}\frac{N^2-3N+2}{6}\\ &=\frac{N-2}{6}. \end{align*}$$

Вправа 1.16

$$\begin{align*} T_N &= \frac{1}{N}\sum_{k=1}^N\left(T_{k-1}+T_{N-k}\right)\\ & = \frac{2}{N}\sum_{k=0}^{N-1}T_k \end{align*}$$ Тепер розглянувши $NT_N - (N-1)T_{N-1}$ ми отримуємо: $$\begin{align*} T_N &= \frac{N+1}{N}T_{N-1}\\ &= \frac{N+1}{N}\cdots\frac{5}{4}T_3\\ &= \frac{N+1}{6} \end{align*}$$ Базовий випадок: $$T_3 = 1/3(1 + 1) = 2/3$$

Вправа 1.17

$$\begin{align*} C_N &= N+1 + \frac{1}{N}\sum_{j=1}^{N}(C_{j-1}+C_{N-j})\\ &= N+1 + \frac{2}{N}\sum_{j=0}^{N-1}C_j\\ &= N+1 + \frac{2}{N}\left(\sum_{j=M+1}^{N-1}C_j + \frac{1}{4}\sum_{1}^M j(j-1)\right) \end{align*}$$ $$\begin{align*} NC_N - (N-1)C_{N-1} &= (N+1)N - N(N-1) + 2C_{N-1}\\ NC_N - (N+1)C_{N-1} &= 2N \end{align*}$$ Використовуємо принцип телескопа складаємо всі рівності від $\frac{C_N}{N+1} - \frac{C_{N-1}}{N}$ до $\frac{C_{M+1}}{M+2} - \frac{\frac{1}{4}M(M-1)}{M+1}$: $$\frac{C_N}{N+1} - \frac{1}{4}\frac{M(M-1)}{M+1} = 2 (H_{N+1} - H_M)$$ $$C_N = \frac{1}{4}(N+1)\frac{M(M-1)}{M+1} + 2(N+1)(H_{N+1} - H_M)$$

Вправа 1.18

$$\begin{align*} C_N &\approx \frac{1}{4}N\frac{M(M-1)}{M+1} + 2N(\ln(N+1) - \ln M)\\ &\approx 2N\ln N + N\left(\frac{1}{4}\frac{M(M-1)}{M+1} - 2 \ln M\right) \end{align*}$$ Мінімуму функція сягає коли $M = 8$.

Вправа 1.19

Кількість порівнянь, яку виконує швидке сортування $\approx 2N\ln N - 1.846N$. При переході з $17$ на $18$, $f(M)$ перестрибує $-1.846$.

Вправа 1.20

Це те саме, що запитати скільки урн міститиме більш ніж одну кулю якщо покласти $10^4$ куль в $10^6$ урн. Досить просто це можна порахувати за допомогою індикаторних змінних. Нехай $X_i=1$ якщо $i$-та урна містить більше ніж одну кулю і $0$ якщо ні. Тоді $E[X_i]=1−P_0−P_1$, де $P_J$ позначає ймовірність, що ця урна містить рівно $j$ куль. $$\begin{align*} P_0 &= \left(\frac{U-1}{U}\right)^B,\\ P_1 &= U\left(\frac{U-1}{U}\right)^{B-1}\left(1-\frac{U-1}{U}\right). \end{align*}$$ Розрахунок в Matlab:

>> U = 10^6;
>> B = 10^4;
>> p = (U-1)/U;
>> (1 - p^B - B*p^(B-1)*(1-p))*U
ans =  49.663

І невеличка симуляція:

    const int U = 1000 * 1000;
    const int B = 10 * 1000;
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, U-1);
    double mean = 0;
    const int roundsCount = 100;
    for (int round = 0; round < roundsCount; ++round) {
        unordered_map<int, int> file;
        for (int i = 0; i < B; ++i) {
            ++file[dis(gen)];
        }
        int duplicated = 0;
        for (auto& el : file) {
            if (el.second > 1) {
                ++duplicated;
            }
        }
        mean += duplicated / static_cast<double>(roundsCount);
    }
    cout << mean << endl;

Вивід не значно відрізняється від отриманого теоретичного результату: 48.87

Вправа 1.21

Чим з меншого діапазону вибираються елементи масиву, тим швидше працює швидке сортування. В крайньому випадку, якщо всі елементи однакові, то розбиття відбувається навпіл і алгоритм працює найшвидше.

Вправа 1.22

Вправа 1.23

Реалізація наведена в цій частині завжди ділить навпіл, і виконує порівняння лише під час злиття і кількість порівнянь не залежить від входових даних. Тому дисперсія дорівнює $0$.