算法是指解决问题的一种方法或一个过程。
算法是若干指令的有穷序列，满足性质：
(1)输入：由外部提供的量作为算法的输入。
(2)输出：算法产生至少一个量作为输出。
(3)确定性：组成算法的每条指令是清晰，无歧义的。
(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
程序是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质(4)
例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。
操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。
分为空间复杂度和时间复杂度，其中时间复杂性最为重要
时间复杂度又分为最坏，最好，平均时间复杂性，其中最坏时间复杂性最有价值。
算法运行时所需要的计算机时间资源的量称为时间复杂性。这个量应该集中反应算法的效率，并从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于要解的问题的规模、算法的输入和算法本身的函数。
时间复杂性具体定义较为复杂，因而引入了复杂性渐近性态的概念。
设 \(T(N)\) 是一个复杂性函数。一般来说，当\(N\)单调递增且趋于\(\infty\)时，\(T(N)\) 也将单调增加且趋于\(\infty\)。对于 \(T(N)\)，如果存在\(T ^ { \sim } ( N )\) ，使得当\(N→∞\)时有\((T(N)?T ^ { \sim } ( N ))/T(N)→0\)，那么，就说\(T ^ { \sim } ( N )\)是\(T(N)\)当 \(N→∞\)时的渐近性态，或称\(T ^ { \sim } ( N )\)为算法当\(N→∞\)的渐近复杂性，而与\(T(N)\)相区别
直观上，\(T ^ { \sim } ( N )\)是 \(T(N)\)中略去低阶项所留下的主项
在这里，主项\(T ^ { \sim } ( N )=3N^2\)
当要比较的两个算法的渐近复杂性的阶不同时，只要能确定出各自的阶，就可以判定出哪一个算法的效率高，不必关心包含在 \(T ^ { \sim } ( N )=3N^2\) 中的常数因子
??为了与此简化的复杂性分析相匹配，需要引入以下渐近意义下的记号\(O , \Omega , \theta \text { 和 } o\)。
1.关于符号\(O\)：如果存在正的常数\(C\)和自然数\(N_0\) ，使得当\(N≥N_0\) 时有\(f(N)≤Cg(N)\) ，则称函数\(f(N)\)当\(N\)充分大时上有界，且\(g(N)\)是它的一个上界，记为\(f(N)=O(g(N))\)。这时还说\(f(N)\)的阶不高于\(g(N)\)的阶。
举几个例子：
\(（1）因为对于所有的 N≥1 有 3N≤4N ，所以有 3N=O(N) ；\)
\(（2）因为当 N≥1 时有 N+1024≤1025N ，所以有 N+1024N=O(N) ；\)
\(（3）因为当 N≥10 时有 2N^2+11N?10≤3N^3 ，所以有 2N^2+11N?10=O(N^2)；\)
2.按照符号\(O\)的定义，容易证明它有如下运算规则：
\(（1）O(f)+O(g)=O(max(f,g))；\)
\(（2）O(f)+O(g)=O(f+g) ；\)
\(（3）O(f)O(g)=O(fg) ；\)
\(（4）如果g(N)=O(f(N)) ，则 O(f)+O(g)=O(f) ；\)
\(（5）O(Cf(N))=O(f(N)) ，其中 C 是一个正的常数；\)
\(（6）f=O(f) 。\)
规则\(（1）O(f)+O(g)=O(max(f,g))；\)的证明:
设 \(F(N)=O(f)\) 。根据符号 \(O\) 的定义，存在正常数 \(C_{1}\) 和自然数 \(N_{1}\), 使得 对所有的 \(N \geqslant N_{1}\), 有 \(F(N) \leqslant C_{1} f(N)\) 。
类似地，设 \(G(N)=O(g)\), 则存在正的常数 \(C_{2}\) 和自然数 \(N_{2}\), 使得对所有的 \(N \geqslant N_{2}\), 有
\(G(N) \leqslant C_{2} g(N)\)
令 \(C_{3}=\max \left\{C_{1}, C_{2}\right\}, N_{3}=\max \left\{N_{1}, N_{2}\right\}, h(N)=\max \{f, g\}\), 则对所有的 \(N \geqslant N_{3}\), 有
\(F(N) \leqslant C_{1} f(N) \leqslant C_{1} h(N) \leqslant C_{3} h(N)\).
类似地，有 \(\quad G(N) \leqslant C_{2} f(N) \leqslant C_{2} h(N) \leqslant C_{3} h(N)\)。
故有：
规则\(（2）O(f)+O(g)=O(f+g) ；\)的证明:
设 \(F(N)=O(f)\) 。根据符号 \(O\) 的定义，存在正常数 \(C_{1}\) 和自然数 \(N_{1}\), 使得 对所有的 \(N \geqslant N_{1}\), 有 \(F(N) \leqslant C_{1} f(N)\) 。
类似地，设 \(G(N)=O(g)\), 则存在正的常数 \(C_{2}\) 和自然数 \(N_{2}\), 使得对所有的 \(N \geqslant N_{2}\), 有
\(G(N) \leqslant C_{2} g(N)\)
令 \(C_{3}=\max \left\{C_{1}, C_{2}\right\}, N_{3}=\max \left\{N_{1}, N_{2}\right\}\), 则对所有的 \(N \geqslant N_{3}\), 有：
故有：
规则$（3）O(f)O(g)=O(fg) $的证明:
设\(F(N)=O(f)\)。根据符号\(O\)的定义，存在正常数\(C_1\)和自然数\(N_1\)，使得对所有的 \(N≥N_1\) ，有 \(F(N)≤C_1f(N)\)。
类似地，设\(G(N)=O(g)\)，则存在正的常数\(C_2\)和自然数\(N_2\) ，使得所有的 \(N≥N_2\) ，有 \(G(N)≤C_2g(N)\) 。
令\(C_3=C_1*C_2, N_{3}=\max \left\{N_{1}, N_{2}\right\}\), 则对所有的\(N≥N_3\) ，有\(F(N)≤C_1f(N),G(N)≤C_2g(N)\)
故有：
原文：https://www.cnblogs.com/pinguo/p/14759197.html