时间复杂度序列的数学证明

我们所知的时间复杂度序列是

O(1)<O(\textrm{log}_{a}n)<O(n)<O(n^{2})<...<O(n^{k})<O(a^{n})<O(n!)

从数学的角度考虑

第一我们知道这个不等式在n充分大时才成立,第二要有限制条件,即k>2,a>1

下面我们给出严格的数学证明

首先证明\textrm{log}_{a}n>1,显然在n>1时总成立


再证明\underset{n \to \infty}{\textrm{lim}} \frac{n^{k}}{a^{n}}=0,即n充分大时,n^{k}<a^{n}
首先因为a>1,我们令a=1+\lambda (\lambda>0)

a^{n}=(1+\lambda )^{n}=1+n\lambda +\textrm{C}_{n}^{2}\lambda ^{2}+...+\lambda ^{n}>\textrm{C}_{n}^2\lambda ^{2}=\frac{n(n-1)}{2}\lambda ^2

n>2时,n-1>\frac{n}{2},将此代入可以得到a^{n}>\frac{n^{2}}{4}\lambda^{2}=\frac{n^{2}(a-1)^{2}}{4}

下面分情况讨论,如果k=1, n \to \infty那么有

\frac{n^{k}}{a^{n}}=\frac{n}{a^{n}}<\frac{n}{\frac{n^{2}(a-1)^{2}}{4}}=\frac{4}{n(a-1)^{2}} \to 0

则对于所有k>0\frac{n^{k}}{a^{n}}=\left [ \frac{n}{(a^{\frac{1}{k}})^{n}} \right ]^{k},而a^{\frac{1}{k}}>1总成立,

所以从上面的讨论可知\underset{n \to \infty }{\textrm{lim}}\frac{n}{(a^{\frac{1}{k}})^{n}}=0

\underset{n \to \infty }{\textrm{lim}}\frac{n^{k}}{a^{n}}=0.


接着证明\underset{n \to \infty}{\textrm{lim}} \frac{a^{n}}{n!}=0,即n充分大时, a^{n}<n!

首先令m为任意一个大于2a的整数,则n>m

0<\frac{a^{n}}{n!}=(\frac{a}{1}\cdot \frac{a}{2}\cdot \cdot \cdot\frac{a}{m})(\frac{a}{m+1}\cdot \frac{a}{m+2}\cdot \cdot \cdot\frac{a}{n})

\frac{a}{1}\cdot \frac{a}{2}\cdot \cdot \cdot\frac{a}{m}<a^{m}, \frac{a}{m+1}<\frac{1}{2} (k+1>2a)

所以\frac{a}{m+1}\cdot \frac{a}{m+2}\cdot \cdot \cdot\frac{a}{n}<(\frac{1}{2})^{n-k}

\frac{a^{n}}{n!}<a^{k}(\frac{1}{2})^{n-k}=\frac{a^{k}}{2^{n}\cdot 2^{-k}}=\frac{(2a)^{k}}{2^{n}},而(2a)^{k}为定值

因为\underset{n \to \infty}{\textrm{lim}}\frac{(2a)^{k}}{2^{n}}=0,所以\underset{n \to \infty}{\textrm{lim}} \frac{a^{n}}{n!}=0.


然后证明\underset{n \to \infty}{\textrm{lim}}\frac{\textrm{log}_{a}n}{n}=0,即n充分大时\textrm{log}_{a}n<n

我们先来证明\underset{n \to \infty}{\textrm{lim}}\sqrt[n]{n}=0

a_{n}=\sqrt[n]{n},则a_{n}>1,根据前面的证明a_{n}^{n}>\frac{n^{2}}{4}(a_{n}-1)^{2},即n>\frac{n^{2}}{4}(\sqrt[n]{n}-1)^{2}

整理后得到\sqrt[n]{n}-1<\frac{2}{\sqrt{n}} \to 0,所以\underset{n \to \infty}{\textrm{lim}}\sqrt[n]{n}=0

现在任取一个正数\varepsilon>0,这个数可以任意小,则a^{\varepsilon}>1(a>1)

可以根据选择的\varepsilon确定一个正整数N值,使得n>N时,\sqrt[n]{n}<a^{\varepsilon}总成立

0<\frac{\textrm{log}_{a}n}{n}<\varepsilon \to 0

所以\underset{n \to \infty}{\textrm{lim}}\frac{\textrm{log}_{a}n}{n}=0.


最后易证\underset{n \to \infty}{\textrm{lim}}\frac{n^{k}}{n^{k+1}}=\frac{1}{n}=0,即n充分大时,n^{k}<n^{k+1}.


综上所述,当n充分大时

 1<\textrm{log}_{a}n<n<n^{2}<...<n^{k}<a^{n}<n! .

发表评论

电子邮件地址不会被公开。 必填项已用*标注