Числові послідовності та границі; нескінченно малі/великі; застосування в алгоритмах

📌 Про що ця тема

Тут перевіряють уміння працювати з числовими послідовностями: знаходити їхні члени за формулою, визначати, чи має послідовність границю (чи «куди вона прямує»), і розуміти поняття нескінченно малих та нескінченно великих величин. Головне застосування для IT — оцінка швидкості зростання функцій і складності алгоритмів (нотація O-велике).

📖 Головне

• Числова послідовність — це функція натурального аргументу: кожному номеру n ставимо у відповідність число aₙ. Задають її формулою n-го члена (aₙ = 1/n) або рекурентно (a₁ задано, aₙ₊₁ через aₙ).

• Арифметична прогресія: кожен наступний = попередній + d. Формула: aₙ = a₁ + (n−1)·d. Сума: Sₙ = (a₁+aₙ)·n/2.

• Геометрична прогресія: кожен наступний = попередній · q. Формула: bₙ = b₁·qⁿ⁻¹. Сума: Sₙ = b₁·(qⁿ−1)/(q−1).

• Границя послідовності — число A, до якого aₙ наближається, коли n → ∞ (різниця |aₙ−A| стає як завгодно малою). Пишуть lim aₙ = A.

• Збіжна послідовність має скінченну границю; розбіжна — ні (або прямує в нескінченність, або коливається).

• Нескінченно мала — послідовність з границею 0 (напр., 1/n, 1/2ⁿ).

• Нескінченно велика — зростає за модулем необмежено, lim = ∞ (напр., n², 2ⁿ).

• Звʼязок: якщо aₙ нескінченно велика і ненульова, то 1/aₙ — нескінченно мала, і навпаки.

• Основні границі: lim 1/n = 0; lim (1 + 1/n) = 1; lim qⁿ = 0 при |q|<1.

• O-велике: оцінка верхньої межі зростання. Відкидаємо константи й молодші доданки. 3n²+5n+2 → O(n²).

• Порядок зростання (від повільного до швидкого): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).

🔢 Як це працює на прикладі

Приклад 1. aₙ = (2n+1)/(n+3). Поділимо чисельник і знаменник на n: (2 + 1/n)/(1 + 3/n). Коли n→∞, дроби 1/n і 3/n → 0, тож границя = 2/1 = 2.

Приклад 2. Цикл: for i=1; i<n; i=i*2. Змінна i подвоюється: 1,2,4,8… Кількість кроків k, доки 2ᵏ ≥ n, тобто k ≈ log₂n. Складність — O(log n).

⚠️ Типові помилки

• Плутають арифметичну і геометричну прогресії: в арифметичній додаємо d, у геометричній множимо на q.

• Вважають, що нескінченно мала = нуль. Ні: це величина, яка лише ПРЯМУЄ до нуля, а члени ненульові.

• Забувають, що lim qⁿ = 0 тільки при |q|<1; при |q|>1 послідовність нескінченно велика.

• В O-великому лишають константи й доданки: пишуть O(2n²) замість O(n²) або O(n²+n) замість O(n²).

• Думають, що вкладений цикл завжди O(n²) — треба дивитися на межі кожного циклу окремо.

🎯 Що завчити напамʼять

• aₙ = a₁+(n−1)d; Sₙ=(a₁+aₙ)n/2.

• bₙ = b₁·qⁿ⁻¹; Sₙ=b₁(qⁿ−1)/(q−1).

• lim 1/n = 0; lim qⁿ=0 при |q|<1.

• Нескінченно мала → границя 0; нескінченно велика → ∞.

• Ієрархія складності: 1, log n, n, n log n, n², 2ⁿ, n!.

🧠 Перевір себе

1. Чому дорівнює lim (3n−1)/(n+2) при n→∞?

2. Послідовність aₙ = 1/n² — нескінченно мала чи велика?

3. Яка складність одинарного циклу for i=0; i<n; i++?

4. b₁=3, q=2 — знайди b₄.

Відповіді: 1 — 3 (поділити на n: (3−1/n)/(1+2/n)→3); 2 — нескінченно мала (прямує до 0); 3 — O(n); 4 — 3·2³=24.