вівторок, 17 квітня 2018 р.

Розв'язки до вправ з "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$.

Немає коментарів:

Дописати коментар