Квадратический рост

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

Примеры

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

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

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

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

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

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

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

Ссылки

^ Мур, Кристофер ; Мертенс, Стефан (2011), Природа вычислений, Oxford University Press, стр. 22, ISBN 9780191620805.
^ Калман, Дэн (1997), Элементарные математические модели: изобилие порядка и проблеск хаоса, Cambridge University Press, стр. 81, ISBN 9780883857076.
^ Эстивилл-Кастро, Владимир (1999), «Сортировка и упорядочение статистики», в Atallah, Михаил Дж. (ред.), Algorithms and Theory of Computation Handbook , Бока-Ратон, Флорида: CRC, стр. 3-1–3-25, MR 1797171.
^ Гриффит, Дэвид; Хикерсон, Дин (2003), «Двумерный кристалл клеточного автомата с иррациональной плотностью», Новые конструкции в клеточных автоматах , St. Fe Inst. Stud. Sci. Complex., Нью-Йорк: Oxford Univ. Press, стр. 79–91, MR 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), «Сортировка и упорядочение статистики», в Atallah, Михаил Дж. (ред.), Algorithms and Theory of Computation Handbook , Бока-Ратон, Флорида: CRC, стр. 3-1–3-25, MR 1797171.

[4] Гриффит, Дэвид; Хикерсон, Дин (2003), «Двумерный кристалл клеточного автомата с иррациональной плотностью», Новые конструкции в клеточных автоматах , St. Fe Inst. Stud. Sci. Complex., Нью-Йорк: Oxford Univ. Press, стр. 79–91, MR 2079729. См. в частности стр. 81: «Размножитель — это любой образец, который растет квадратично, создавая постоянный поток копий второго объекта, каждая из которых создает поток третьего».

[5] Рольфс, Джеффри Х. (2003), «3.3 Закон Меткалфа», Эффекты присоединения к большинству в высокотехнологичных отраслях, MIT Press, стр. 29–30, ISBN 9780262681384.