Kvadratický růst - Quadratic growth

v matematika se říká, že funkce nebo sekvence vykazuje kvadratický růst když jsou jeho hodnoty úměrný do náměstí argumentu funkce nebo pozice sekvence. „Kvadratický růst“ často obecně znamená „kvadratický růst limitu“, protože pozice argumentu nebo sekvence jde do nekonečna - v velká notace Theta, F(X) = Θ (X²).^[1] To lze definovat jak spojitě (pro funkci reálné proměnné se skutečnou hodnotou), tak diskrétně (pro posloupnost reálných čísel, tj. Funkce se skutečnou hodnotou proměnné celého čísla nebo přirozeného čísla).

Příklady

Mezi příklady kvadratického růstu patří:

Žádný kvadratický polynom.
Určitý celočíselné sekvence tak jako trojúhelníková čísla. The ntoto trojúhelníkové číslo má hodnotu n(n+1) / 2, přibližně n²/2.

Pro skutečnou funkci reálné proměnné je kvadratický růst ekvivalentní s tím, že druhá derivace je konstantní (tj. Třetí derivace je nulová), a tedy funkce s kvadratickým růstem jsou přesně kvadratické polynomy, protože se jedná o jádro třetího derivátového operátora D³. Podobně pro sekvenci (skutečná funkce proměnné celého čísla nebo přirozeného čísla) je kvadratický růst ekvivalentní s druhou konečný rozdíl být konstantní (třetí konečný rozdíl je nula),^[2] a tedy sekvence s kvadratickým růstem je také kvadratickým polynomem. Ve skutečnosti je sekvence s celočíselnou hodnotou s kvadratickým růstem polynom v nule, první a druhé binomický koeficient s celočíselnými hodnotami. Koeficienty lze určit pomocí Taylorův polynom (je-li spojitá) nebo Newtonův polynom (pokud je diskrétní).

Algoritmické příklady zahrnují:

Doba, kterou v nejhorším případě jistě zabere algoritmy, jako třídění vložení, jako funkce vstupní délky.^[3]
Počet živých buněk vyplňujících prostor buněčný automat vzory jako chovatel, jako funkce počtu časových kroků, pro které je vzor simulován.^[4]
Metcalfeův zákon uvádí, že hodnota komunikační sítě kvadraticky roste v závislosti na jejím počtu uživatelů^[5]

Viz také

Exponenciální růst

Reference

^ Moore, Cristopher; Mertens, Stephan (2011), Povaha výpočtu Oxford University Press, s. 22, ISBN 9780191620805.
^ Kalman, Dan (1997), Základní matematické modely: Pořádek a pohled na chaos, Cambridge University Press, str. 81, ISBN 9780883857076.
^ Estivill-Castro, Vladimir (1999), "Třídění a statistika objednávek", v Atallah, Michail J. (vyd.), Příručka Algoritmy a teorie výpočtu, Boca Raton, Florida: CRC, s. 3-1–3-25, PAN 1797171.
^ Griffeath, David; Hickerson, Dean (2003), „Dvourozměrný krystal buněčného automatu s iracionální hustotou“, Nové konstrukce v celulárních automatech, St. Fe Inst. Stud. Sci. Complex., New York: Oxford Univ. Press, str. 79–91, PAN 2079729. Viz zejména str. 81: "Chovatel je jakýkoli vzor, který kvadraticky roste vytvářením stálého proudu kopií druhého objektu, z nichž každý vytváří proud třetího."
^ Rohlfs, Jeffrey H. (2003), „3.3 Metcalfe's law“, Účinky rozjetého vlaku v průmyslových odvětvích s vysokou technologií, MIT Press, str. 29–30, ISBN 9780262681384.

Tento matematická analýza –Vztahující se článek je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[1] Moore, Cristopher; Mertens, Stephan (2011), Povaha výpočtu Oxford University Press, s. 22, ISBN 9780191620805.

[2] Kalman, Dan (1997), Základní matematické modely: Pořádek a pohled na chaos, Cambridge University Press, str. 81, ISBN 9780883857076.

[3] Estivill-Castro, Vladimir (1999), "Třídění a statistika objednávek", v Atallah, Michail J. (vyd.), Příručka Algoritmy a teorie výpočtu, Boca Raton, Florida: CRC, s. 3-1–3-25, PAN 1797171.

[4] Griffeath, David; Hickerson, Dean (2003), „Dvourozměrný krystal buněčného automatu s iracionální hustotou“, Nové konstrukce v celulárních automatech, St. Fe Inst. Stud. Sci. Complex., New York: Oxford Univ. Press, str. 79–91, PAN 2079729. Viz zejména str. 81: "Chovatel je jakýkoli vzor, který kvadraticky roste vytvářením stálého proudu kopií druhého objektu, z nichž každý vytváří proud třetího."

[5] Rohlfs, Jeffrey H. (2003), „3.3 Metcalfe's law“, Účinky rozjetého vlaku v průmyslových odvětvích s vysokou technologií, MIT Press, str. 29–30, ISBN 9780262681384.

[1]

[2]

[3]

[4]

[5]