算法是指解决问题的一种方法或一个过程。
算法是若干指令的有穷序列,满足性质:
(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