У математиці кажуть, що функція або послідовність виявляють квадратичне зростання, якщо її значення пропорційні квадрату аргументу функції або порядковому номеру члена послідовності. Часто термін «квадратичне зростання» означає загальніше «квадратичне зростання в границі», коли аргумент функції або порядковий номер члена послідовності прямує нескінченності — у нотації великого Тета, .. Це можна визначити як неперервно (для дійснозначної функції дійсної змінної), так і дискретно (для послідовності дійсних чисел, тобто дійснозначної функції цілої або натуральної змінної).

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

будь-який квадратний многочлен; деякі послідовності цілих чисел, наприклад трикутні числа. Значення -го трикутного числа , що приблизно дорівнює .

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

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

Час, якого в найгіршому випадку потребують деякі алгоритми, такі як сортування включенням, як функція довжини вхідних даних.. Кількість живих клітин у шаблонах клітинних автоматів, що заповнюють простір, наприклад, розмножувача, як функція кількості кроків моделювання.. See in particular p. 81: «A breeder is any pattern which grows quadratically by creating a steady stream of copies of a second object, each of which creates a stream of a third.» Закон Меткалфа, згідно з яким вартість комунікаційної мережі зростає квадратично залежно від кількості користувачів..

Див. також Експоненційне зростання

Примітки