Квадратичне зростання
У математиці кажуть, що функція або послідовність виявляють квадратичне зростання, якщо її значення пропорційні квадрату аргументу функції або порядковому номеру члена послідовності. Часто термін «квадратичне зростання» означає загальніше «квадратичне зростання в границі», коли аргумент функції або порядковий номер члена послідовності прямує нескінченності — у нотації великого Тета, .[1] Це можна визначити як неперервно (для дійснозначної функції дійсної змінної), так і дискретно (для послідовності дійсних чисел, тобто дійснозначної функції цілої або натуральної змінної).
Прикладами квадратичного зростання є:
- будь-який квадратний многочлен;
- деякі послідовності цілих чисел, наприклад трикутні числа. Значення -го трикутного числа , що приблизно дорівнює .
Для дійснозначної функції дійсної змінної квадратичне зростання еквівалентне тому, що її друга похідна є сталою (тобто третя похідна дорівнює нулю), і, отже, функції з квадратичним зростанням є точно квадратними многочленами, оскільки вони є ядром оператора третьої похідної . Подібно, для послідовності (дійснозначної функції цілої або натуральної змінної) квадратичне зростання еквівалентне тому, що друга скінченна різниця є сталою (третя скінченна різниця дорівнює нулю),[2] і, отже, послідовність із квадратичним зростанням також є квадратним многочленом. Дійсно, цілочисельна послідовність із квадратичним зростанням є многочленом із цілими значеннями нульового, першого та другого біноміальних коефіцієнтів. Коефіцієнти можна визначити, взявши многочлен Тейлора (для неперервного) або многочлен Ньютона (для дискретного).
Приклади алгоритмів:
- Час, якого в найгіршому випадку потребують деякі алгоритми, такі як сортування включенням, як функція довжини вхідних даних.[3]
- Кількість живих клітин у шаблонах клітинних автоматів, що заповнюють простір, наприклад, розмножувача, як функція кількості кроків моделювання.[4]
- Закон Меткалфа, згідно з яким вартість комунікаційної мережі зростає квадратично залежно від кількості користувачів.[5]
- ↑ Moore, Cristopher; Mertens, Stephan (2011), The Nature of Computation, Oxford University Press, с. 22, ISBN 9780191620805.
- ↑ Kalman, Dan (1997), Elementary Mathematical Models: Order Aplenty and a Glimpse of Chaos, Cambridge University Press, с. 81, ISBN 9780883857076.
- ↑ Estivill-Castro, Vladimir (1999), Sorting and order statistics, у Atallah, Mikhail J. (ред.), Algorithms and Theory of Computation Handbook, Boca Raton, Florida: CRC, с. 3-1—3-25, MR 1797171.
- ↑ Griffeath, David; Hickerson, Dean (2003), A two-dimensional cellular automaton crystal with irrational density, New constructions in cellular automata, St. Fe Inst. Stud. Sci. Complex., New York: Oxford Univ. Press, с. 79—91, MR 2079729. 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.»
- ↑ Rohlfs, Jeffrey H. (2003), 3.3 Metcalfe's law, Bandwagon Effects in High-technology Industries, MIT Press, с. 29—30, ISBN 9780262681384.