1.时间复杂性


最优算法: 时间复杂性O(n log n),空间复杂性O(1)

1)$O$符号(上界)

  令f(n)和g(n)是从自然数集到非负实数集的两个函数，若存在一个自然数和一个常数c>0，使得:

则f(n)为$O$(g(n))。

  若    存在

那么:



2)$\Omega$符号(下界)

  令f(n)和g(n)是从自然数集到非负实数集的两个函数，若存在一个自然数和一个常数c>0，使得:

则f(n)为$\Omega$(g(n))。

  若    存在

那么:



3)$\Theta$符号

  令f(n)和g(n)是从自然数集到非负实数集的两个函数，若存在一个自然数$n_{0}$和常数$c_1,c_2$使得:

则f(n)为$\Theta$(g(n))。

  若    存在

那么:

Summary: 可以认为$O$类似于 $\leq$, $\Omega$类似于$\geq$,$\Theta$类似于=

举例:

$f(n)=\log{n^2}$

$$ \because \lim_{n\to\infty}\frac{\log{n^2}}{n}=\lim_{n\to\infty}\frac{2\log{n}}{n}=\frac{2}{\ln{2}}\lim_{n\to\infty}\frac{1}{n}=0 \\\\ $$ $$ \therefore f(n)=O(n)\quad but \quad not \quad \Omega(n) or \Theta(n) $$ $$ \because \log{n^2}=2\log{n} \therefore\log{n^2}=\Theta(\log{n}) \\\\ \therefore \log{n^k}=\Theta(n)\\ $$

$ \sum_{j=1}^{n}\log{j}$


$$ \because \sum_{j=1}^{n}\log{j} \leq \sum_{j=1}^{n}\log{n} $$ $$ \therefore \sum_{j=1}^{n}\log{j} = O(n\log{n}) $$ $$ 又 \because \sum_{j=1}^{n}\log{j} \geq \sum_{j=1}^{\frac{n}2}\log{\frac{n}2}=\frac{n}{2}\log{\frac{n}2}=\frac{n}{2}\log{n} -\frac{n}{2} $$ $$ \therefore \sum_{j=1}^{n} = \Omega(n\log{n}) $$ $$ \therefore \sum_{j=1}^{n} = \Theta(n\log{n}) $$

$\log{n!}$


$$ \because \log{n!}=\log({n*(n-1)*\dots*1})=\log n *\log(n-1) *\dots*\log 1=\sum_{j=1}^{n}\log j $$ $$ \therefore \log n! = \Theta (n\log n) $$

3)$o$符号

用f(n)$\prec$g(n)表示f(n)是o(g(n))的：