В математике , функция или последовательность называются проявляет квадратичный рост , когда его значение пропорционально к квадрату функции аргумента или позиции последовательности. «Квадратичный рост» часто означает в более общем смысле «квадратичный рост в пределе», поскольку позиция аргумента или последовательности стремится к бесконечности - в большой тета-нотации ,. [1] Это может быть определено как непрерывно (для действительной функции действительной переменной), так и дискретно (для последовательности действительных чисел, т. Е. Действительнозначная функция целочисленной или натуральной числовой переменной).
Примеры
Примеры квадратичного роста:
- Любой квадратичный многочлен .
- Определенные последовательности целых чисел, например треугольные числа . Вое треугольное число имеет значение , примерно .
Для действительной функции действительной переменной квадратичный рост эквивалентен тому, что вторая производная постоянна (т. Е. Третья производная равна нулю), и, таким образом, функции с квадратичным ростом являются в точности квадратичными многочленами, поскольку они являются ядром третьей производной оператор. Точно так же для последовательности (действительной функции от целочисленной или натуральной числовой переменной) квадратичный рост эквивалентен тому, что вторая конечная разность является постоянной (третья конечная разность равна нулю) [2], и, следовательно, последовательность с квадратичным ростом также квадратичный многочлен. Действительно, целочисленная последовательность с квадратичным ростом является полиномом от нулевого, первого и второго биномиальных коэффициентов с целыми значениями. Коэффициенты можно определить, взяв полином Тейлора (если он непрерывен) или полином Ньютона (если он дискретен).
Алгоритмические примеры включают:
- Время, затрачиваемое в худшем случае определенными алгоритмами , такими как сортировка вставкой , в зависимости от длины ввода. [3]
- Число живых клеток в заполняющих пространство паттернах клеточных автоматов , таких как заводчик , как функция количества временных шагов, для которых моделируется паттерн. [4]
- Закон Меткалфа, гласящий, что ценность коммуникационной сети квадратично растет в зависимости от количества ее пользователей. [5]
Смотрите также
Рекомендации
- ^ Мур, Кристофер ; Мертенс, Стефан (2011), Природа вычислений , Oxford University Press, стр. 22, ISBN 9780191620805 CS1 maint: обескураженный параметр ( ссылка ).
- ^ Калман, Дэн (1997), Элементарные математические модели: изобилие порядка и проблеск хаоса , Cambridge University Press, стр. 81, ISBN 9780883857076.
- ^ Эстивилл-Кастро, Владимир (1999), «Статистика сортировки и упорядочения», в Аталлахе, Михаил Дж. (Редактор), Справочник по алгоритмам и теории вычислений , Бока-Ратон, Флорида: CRC, стр. 3-1–3-25. , Руководство по ремонту 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.