Kvadratisk tillväxt

För andra användningar av ordet "kvadratiskt" i matematik, se Kvadratiskt (disambiguation) .

I matematik sägs en funktion eller sekvens uppvisa kvadratisk tillväxt när dess värden är proportionella mot kvadraten på funktionsargumentet eller sekvenspositionen. "Kvadratisk tillväxt" betyder ofta mer allmänt "kvadratisk tillväxt i gränsen " , eftersom argumentet eller sekvenspositionen går till oändlighet – i big Theta notation , $f(x)=\ Theta (x^{2})$ . Detta kan definieras både kontinuerligt (för en reellt värderad funktion av en reell variabel) eller diskret (för en sekvens av reella tal, dvs. en reellt värderad funktion av en heltalsvariabel eller naturlig talvariabel ).

Exempel

Exempel på kvadratisk tillväxt inkluderar:

• Vilket kvadratiskt polynom som helst .
• Vissa heltalssekvenser som triangulära tal . Det ${\displaystyle n}:$ e triangulära talet har värdet $/2}$$\displaystyle n(n+1)/2}$ , ungefär .

För en reell funktion av en reell variabel är kvadratisk tillväxt ekvivalent med att andraderivatan är konstant (dvs tredjederivatan är noll), och således är funktioner med kvadratisk tillväxt exakt de kvadratiska polynomen, eftersom dessa är kärnan i tredjederivatan operator $D^{3}$ . På liknande sätt, för en sekvens (en reell funktion av ett heltal eller naturlig talvariabel), är kvadratisk tillväxt ekvivalent med att den andra finita skillnaden är konstant (den tredje finita skillnaden är noll), och därför är en sekvens med kvadratisk tillväxt också ett kvadratiskt polynom . Faktum är att en heltalsvärderad sekvens med kvadratisk tillväxt är ett polynom i den nollte, första och andra binomialkoefficienten med heltalsvärden. Koefficienterna kan bestämmas genom att ta Taylor-polynomet (om det är kontinuerligt) eller Newton-polynomet (om det är diskret).

Algoritmiska exempel inkluderar:

• Hur lång tid det tar i värsta fall av vissa algoritmer , såsom insättningssort , som en funktion av inmatningslängden.
• Antalet levande celler i rymdfyllande cellulära automatmönster, såsom uppfödaren , som en funktion av antalet tidssteg för vilka mönstret simuleras.
• Metcalfes lag som säger att värdet av ett kommunikationsnätverk växer kvadratiskt som en funktion av antalet användare.

Se även

• Exponentiell tillväxt