Квадратичный рост

В математике говорят , что функция или последовательность демонстрируют квадратичный рост , когда ее значения пропорциональны квадрату аргумента функции или позиции последовательности. «Квадратичный рост» часто означает в более общем смысле «квадратичный рост в пределе », поскольку позиция аргумента или последовательности стремится к бесконечности – в большой записи Тета . ^[1] Это может быть определено как непрерывно (для вещественной функции действительной переменной), так и дискретно (для последовательности действительных чисел, т. е. вещественной функции целочисленной или натуральной числовой переменной). ${\displaystyle f(x)=\Theta (x^{2})}$

Примеры

Примеры квадратичного роста включают:

• Любой квадратичный полином .
• Определенные целочисленные последовательности , такие как треугольные числа . Треугольное число имеет значение приблизительно . ${\displaystyle n}$ ${\displaystyle n(n+1)/2}$ ${\displaystyle n^{2}/2}$

Для действительной функции действительной переменной квадратичный рост эквивалентен постоянной второй производной (т. е. третьей производной , равной нулю), и, таким образом, функции с квадратичным ростом являются в точности квадратичными полиномами, поскольку они являются ядром третьей производной. оператор . Аналогично, для последовательности (действительной функции целочисленной или натуральной числовой переменной) квадратичный рост эквивалентен тому, что вторая конечная разность постоянна (третья конечная разность равна нулю), ^[2] и, таким образом, последовательность с квадратичным ростом также является квадратичный полином. Действительно, целочисленная последовательность с квадратичным ростом представляет собой многочлен от нулевого, первого и второго биномиальных коэффициентов с целыми значениями. Коэффициенты можно определить, взяв полином Тейлора (если он непрерывен) или полином Ньютона (если дискретен). ${\displaystyle D^{3}}$

Алгоритмические примеры включают в себя:

• Количество времени, затрачиваемое в худшем случае на работу определенных алгоритмов , таких как сортировка вставками , в зависимости от длины входных данных. ^[3]
• Количество живых клеток в заполняющих пространство шаблонах клеточных автоматов, таких как бридер , в зависимости от количества временных шагов, для которых моделируется шаблон. ^[4]
• Закон Меткалфа, гласящий, что ценность сети связи растет квадратично в зависимости от количества ее пользователей. ^[5]

Смотрите также

• Экспоненциальный рост

Рекомендации

1. Мур, Кристофер ; Мертенс, Стефан (2011), Природа вычислений, Oxford University Press, стр. 22, ISBN 9780191620805.
2. Калман, Дэн (1997), Элементарные математические модели: изобилие порядка и взгляд на хаос, Cambridge University Press, стр. 81, ISBN 9780883857076.
3. Эстивилл-Кастро, Владимир (1999), «Статистика сортировки и порядка», в Аталлахе, Михаил Дж. (ред.), Справочник по алгоритмам и теории вычислений , Бока-Ратон, Флорида: CRC, стр. 3-1–3- 25, МР  1797171.
4. Гриффит, Дэвид; Хикерсон, Дин (2003), «Двумерный кристалл клеточного автомата с иррациональной плотностью», Новые конструкции в клеточных автоматах , St. Fe Inst. Стад. наук. Комплекс., Нью-Йорк: Оксфордский университет. Пресс, стр. 79–91, МР  2079729.. См., в частности, стр. 81: «Селекционер — это любой шаблон, который растет квадратично, создавая постоянный поток копий второго объекта, каждая из которых создает поток третьего».
5. Рольфс, Джеффри Х. (2003), «3.3 Закон Меткалфа», Эффекты победителя в высокотехнологичных отраслях, MIT Press, стр. 29–30, ISBN 9780262681384.