Квадратичне зростання

У математиці кажуть, що функція або послідовність виявляють квадратичне зростання, якщо її значення пропорційні квадрату аргументу функції або порядковому номеру члена послідовності. Часто термін «квадратичне зростання» означає загальніше «квадратичне зростання в границі», коли аргумент функції або порядковий номер члена послідовності прямує нескінченності — у нотації великого Тета, $f(x)=\mathrm{\Theta }(x^2)$. Це можна визначити як неперервно (для дійснозначної функції дійсної змінної), так і дискретно (для послідовності дійсних чисел, тобто дійснозначної функції цілої або натуральної змінної).

Приклади

Прикладами квадратичного зростання є:

• будь-який квадратний многочлен;
• деякі послідовності цілих чисел, наприклад трикутні числа. Значення $n$-го трикутного числа $n(n+1)/2$, що приблизно дорівнює $n^2/2$.

Для дійснозначної функції дійсної змінної квадратичне зростання еквівалентне тому, що її друга похідна є сталою (тобто третя похідна дорівнює нулю), і, отже, функції з квадратичним зростанням є точно квадратними многочленами, оскільки вони є ядром оператора третьої похідної $D^3$. Подібно, для послідовності (дійснозначної функції цілої або натуральної змінної) квадратичне зростання еквівалентне тому, що друга скінченна різниця є сталою (третя скінченна різниця дорівнює нулю), і, отже, послідовність із квадратичним зростанням також є квадратним многочленом. Дійсно, цілочисельна послідовність із квадратичним зростанням є многочленом із цілими значеннями нульового, першого та другого біноміальних коефіцієнтів. Коефіцієнти можна визначити, взявши многочлен Тейлора (для неперервного) або многочлен Ньютона (для дискретного).

Приклади алгоритмів:

• Час, якого в найгіршому випадку потребують деякі алгоритми, такі як сортування включенням, як функція довжини вхідних даних.
• Кількість живих клітин у шаблонах клітинних автоматів, що заповнюють простір, наприклад, розмножувача, як функція кількості кроків моделювання.
• Закон Меткалфа, згідно з яким вартість комунікаційної мережі зростає квадратично залежно від кількості користувачів.

Див. також

• Експоненційне зростання