首页 > 编程语言 > 详细

第一章:算法概述

时间:2021-05-12 15:04:24      阅读:13      评论:0      收藏:0      [点我收藏+]

第一章:算法概述

1.1算法与程序

算法是指解决问题的一种方法或一个过程。
算法是若干指令的有穷序列,满足性质:
(1)输入:由外部提供的量作为算法的输入。
(2)输出:算法产生至少一个量作为输出。
(3)确定性:组成算法的每条指令是清晰,无歧义的。
(4)有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的。

程序是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质(4)
例如操作系统,是一个在无限循环中执行的程序,因而不是一个算法。
操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。

1.2算法复杂性分析

分为空间复杂度和时间复杂度,其中时间复杂性最为重要

时间复杂度又分为最坏,最好,平均时间复杂性,其中最坏时间复杂性最有价值

时间复杂度

算法运行时所需要的计算机时间资源的量称为时间复杂性。这个量应该集中反应算法的效率,并从运行该算法的实际计算机中抽象出来。换句话说,这个量应该是只依赖于要解的问题的规模、算法的输入和算法本身的函数。

时间复杂性具体定义较为复杂,因而引入了复杂性渐近性态的概念。

\(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 ( N ) - T ^ { \sim } ( N ) ) / T ( N ) = \frac { 4 N \operatorname { log } N + 7 } { 3 N ^ { 2 } + 4 N \operatorname { log } N + 7 } \rightarrow 0 ( N \rightarrow \infty ) \]

在这里,主项\(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)\)

故有:

\[\quad \begin{aligned} O(f)+O(g)=F(N)+G(N) \leqslant C_{3} h(N)+C_{3} h(N) =& \\2 C_{3} h(N)=O(h)=O(\max (f, g)) \end{aligned} \]

规则\((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}\), 有:

\[F(N) \leqslant C_{1} f(N) \leqslant C_{3} f(N) G(N) \leqslant C_{2} g(N) \leqslant C_{3} g(N) \]

故有:

\[O(f)+O(g)=F(N)+G(N)≤C_3f(N)+C_3g(N)\\=C_3(f(N)+g(N))=O(f+g) \]

规则$(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)\)
故有:

\[O(f)*O(g)=F(N)*G(N)≤C_1f(N)*C_2g(N)\\=C_3*f(N)*g(N)=O(f*g) \]

第一章:算法概述

原文:https://www.cnblogs.com/pinguo/p/14759197.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!