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

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

Примеры [ править ]

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

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

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

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

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

См. также [ править ]

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

Ссылки [ править ]

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

Эта математическому анализу, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее .

[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 .

[1]

[2]

[3]

[4]

[5]