Задачі: Оцінка складності алгоритмів¶

Практичні задачі на тему аналізу складності алгоритмів.

Формат задач

В задачах на оцінку складності потрібно визначити часову складність у нотації \(O(\ldots)\). В задачах на доведення потрібно знайти конкретні значення \(C\) і \(n_0\).

Оцінка складності фрагментів коду¶

Задача 1: Простий цикл

Визначте складність:

int sum = 0;
for (int i = 0; i < n; ++i) {
    sum += i;
}

Задача 2: Вкладені цикли

Визначте складність:

int count = 0;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        count++;
    }
}

Задача 3: Залежний внутрішній цикл

Визначте складність:

int count = 0;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
        count++;
    }
}

Підказка: скільки разів виконається внутрішній цикл для кожного \(i\)? Порахуйте суму \(0 + 1 + 2 + \ldots + (n-1)\).

Задача 4: Цикл із поділом

Визначте складність:

int x = n;
while (x > 1) {
    x = x / 3;
}

Задача 5: Послідовні фрагменти

Визначте складність:

// Fragment 1
for (int i = 0; i < n; ++i) {
    // O(1) operation
}

// Fragment 2
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        // O(1) operation
    }
}

// Fragment 3
for (int i = 0; i < 1000; ++i) {
    // O(1) operation
}

Задача 6: Цикл із множенням

Визначте складність:

int x = 1;
while (x < n) {
    x = x * 2;
}

Задача 7: Хитрий вкладений цикл

Визначте складність:

for (int i = 1; i < n; i *= 2) {
    for (int j = 0; j < n; ++j) {
        // O(1) operation
    }
}

Підказка: скільки разів виконається зовнішній цикл?

Доведення за означенням¶

Задача 8: Довести \(5n + 7 = O(n)\)

Знайдіть конкретні значення \(C > 0\) і \(n_0\), такі що для всіх \(n \geq n_0\):

\[5n + 7 \leq C \cdot n\]

Задача 9: Довести \(n^2 + 3n + 1 = \Theta(n^2)\)

Покажіть, що \(n^2 + 3n + 1 = O(n^2)\) і \(n^2 + 3n + 1 = \Omega(n^2)\).

Для кожної частини знайдіть конкретні значення констант.

Задача 10: Довести \(\log n = O(n)\)

Покажіть за означенням, що існують \(C\) і \(n_0\), для яких \(\log_2 n \leq C \cdot n\) при всіх \(n \geq n_0\).

Підказка: спробуйте \(C = 1\), \(n_0 = 1\) і використайте той факт, що \(\log_2 n \leq n\) для всіх \(n \geq 1\).

Задача 11: Чи правда, що \(n^2 = O(n)\)?

Доведіть або спростуйте.

Підказка: припустіть, що існують \(C\) і \(n_0\), та покажіть суперечність.

Рекурсивна складність¶

Задача 12: Рекурсивний факторіал

Визначте складність:

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

Запишіть рекурентне співвідношення і розкрийте його.

Задача 13: Рекурсивна степінь

Визначте складність обох варіантів:

Варіант А (лінійна рекурсія):

double power(double x, int n) {
    if (n == 0) return 1;
    return x * power(x, n - 1);
}

Варіант Б (швидке піднесення):

double fast_power(double x, int n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        double half = fast_power(x, n / 2);
        return half * half;
    }
    return x * fast_power(x, n - 1);
}

Задача 14: Побудуйте дерево рекурсії

Побудуйте дерево рекурсії для \(T(n) = 3T(n/3) + O(n)\) та визначте загальну складність.

Підказка: скільки роботи виконується на кожному рівні? Скільки рівнів?

Задача 15: Рекурсія з двома гілками

Визначте складність:

void mystery(int n) {
    if (n <= 1) return;
    mystery(n / 2);
    mystery(n / 2);
    for (int i = 0; i < n; ++i) {
        // O(1)
    }
}

Підказка: запишіть рекурентне співвідношення. Що це нагадує?

Порівняння росту функцій та границі¶

Задача 16: Знайти границю

Обчисліть:

\[\lim_{x \to \infty} \frac{\log x}{x^2}\]

Використайте правило Лопіталя.

Задача 17: Знайти границю

Обчисліть:

\[\lim_{x \to \infty} \frac{x^3}{5^x}\]

Скільки разів потрібно застосувати правило Лопіталя?

Задача 18: Порівняти порядки росту

Розташуйте функції в порядку зростання (від найповільнішої до найшвидшої):

\[n^2, \quad 2^n, \quad n \log n, \quad \log n, \quad n!, \quad n, \quad 1, \quad \sqrt{n}\]

Задача 19: Визначити відношення

Для кожної пари визначте: \(f(n) = O(g(n))\), \(f(n) = \Omega(g(n))\), чи \(f(n) = \Theta(g(n))\)?

a) \(f(n) = n^2\), \(g(n) = n^3\)
b) \(f(n) = 2n + 100\), \(g(n) = n\)
c) \(f(n) = \log_2 n\), \(g(n) = \log_{10} n\)

Підказка для (c): пам'ятайте формулу переходу між основами логарифмів.

Практичні задачі¶

Задача 20: Який алгоритм ефективніший?

Алгоритм A має складність \(100n\). Алгоритм B має складність \(n^2\).

a) Для якого найменшого \(n\) алгоритм A стає швидшим?
b) Якщо комп'ютер виконує \(10^9\) операцій на секунду, за який час кожен алгоритм обробить \(n = 10^6\) елементів?

Задача 21: Максимальний розмір за обмежений час

Комп'ютер виконує \(10^8\) операцій на секунду. За 1 секунду потрібно обробити максимально великий масив. Який максимальний \(n\) для кожного алгоритму?

a) \(O(n)\)
b) \(O(n \log n)\)
c) \(O(n^2)\)
d) \(O(2^n)\)

Лекція: Оцінка складності алгоритмів | Додатково: Master theorem