算法设计与分析【一】

一、基本概念


1、什么是算法

算法是为求解一个问题所需要遵循的、被清楚指定的简单指令集合。

  • 每条指令的意义都是确定的
  • 具有零个或多个输入
  • 产生若干个输出
  • 执行时间是有限的 (终止性)

2、算法和程序的区别及描述方法

(1)算法和程序的区别

程序是某个算法或过程的在计算机上的一个具体的实现。

程序是依赖于程序设计语言的,甚至依赖于计算机结构的。

  • 例如C++和Python的排序算法,可能由于Python的特性而语法上有所不同,

算法是脱离具体的计算机结构和程序设计语言的。

(2)描述方法

自然语言表示算法贴近人类思维,易于理解主旨,但是表述不够精准,存在模糊歧义,编程语言表示算法精准表达逻辑,规避表述歧义,但是受限语法细节,增大理解难度。故引入伪代码,关注算法本质,便于书写阅读

学会写伪代码

3、算法的复杂性和分析

算法的复杂性是指算法运行时所需要的计算机资源的量多少,所需资源量越多则复杂性越高,反之所需资源量越少则复杂性越低。其中最为重要的是:

  • 时间复杂性:需要时间的资源量
  • 空间复杂性:需要空间的资源量

这里人们通常更为关注的是时间复杂性

算法的复杂性取决于:求解问题的规模(倾向于数的大小、数字的量)、具体的输入数据(倾向于数据的状态对于算法的影响)、算法本身的设计

若令N、I、和A分别表示问题的规模、具体的输入和算法本身,则C = F(N, I, A)或 C = F( N, I)

其中:ti为执行抽象计算机的第i种指令一次所需要的时间,这里假定抽象计算机共有k种指令。ei(N, I)为经过统计后得到的执行抽象计算机的第i种指令的次数。

对于具体的输入数据带来的影响,(倾向于数据的状态对于算法的影响)我们又划分出最坏、最好、平均三种分析。最好情况使用价值不大,平均分析需要概率相关知识和多重复杂运算,暂时不做分析。所以我们一般只考虑最坏情况

问:分析算法的时间复杂度,不是应该考虑时间吗?那么加法乘法除法等运算不同的运算不是时间不一样吗?为什么都按一次基本运算考虑?

答:因为我们是比较算法的效率,所以可以假设在同一台机上跑,且假设这台机器的性能永远不出现一丝变化对于所有算法,每次执行这些基本操作的时间都相同。我们就控制了变量

问:加减法和乘除法的操作怎么都能化为1呢?乘法不应该比加法慢很多吗?假如一个算法乘法多一个算法加法多怎么能够都按照“1”来想呢?

答:这是从某种角度上来说的一个解释,提供某种程度上的合理性:根据上一个假设:同一台机上跑,且假设这台机器的性能永远不出现一丝变化。而CPU的频率是固定的,所以在这个抽象计算机上,所有操作都是根据消耗的周期来想的。而由于工艺改进,和其他编译器等等其他因素,所以我们可以这样想。例:在九十年代奔腾处理器出现之前是加法比乘法快,但是奔腾处理器及之后的某些处理器,这两种操作是一样快的。其次编译器的优化,你写的代码编译后不一定是按照你编的执行的。

正常解释:要精确计算算法执行时所消耗的资源是非常繁琐,代价较大,甚至说不太切于实际的。

而在排除掉机器影响,且我们只专注最坏情况下,影响因素就只有规模了,我们以后将它称为T(n),对于输入规模足够大的时候,我只要关心算法所消耗的增加量级,也就是研究算法的渐进效率。

我们都知道当问题规模足够大的时候,算法的运行时间将主要取决于时间表达式的最高次项,而上图就是这样分析复杂度的数学基础支撑,也就是渐进分析,这样我们分析,只用分析规模n的最高阶就可以了,并且不用关系它的常数因子,而它的表示方法O(n)是一种渐进符号,关于渐进表示法,这篇文章写的很好。

同时到了这里一定要明确:

大O符号表示法并不是用于来真实代表算法的执行时间的,它是用来表示代码执行时间的增长变化趋势的

问:为什么要分析算法的渐进效率,而不是直接按照输入规模直接计算效率进行比较?

答:很直观的原因就是,当输入规模小的时候,各种算法间的差距并不会太大,对于大部分应用程序来讲,这些差距都可以被忽略。现实原因是,要精确计算算法执行时所消耗的资源是非常繁琐,代价较大,甚至说不太切于实际的。

4、关于渐进符号

推荐文章:

算法的渐进效率分析 和 渐进符号大O、大Ω、大θ、小o、小ω

算法导论——渐近记号Θ、Ο、o、Ω、ω详解

算法分析与设计的高等数学基础

这里摘要一些:

  • 渐进符号描述的表达式 表示 一个函数集合。而在渐进分析中的 ”=“更倾向于“∈ ”的意思。打个比方:渐进表达式 f(n) = O(g(n))所表达的意思是,O(g(n)) = [ f(n),h(n)…..g(n) ]; f(n) ∈ O(g(n))

  • 通俗的:对 O的定义是为了数学语言精确说明:n满足一定条件范围内,函数f(n)的阶不高于函数g(n)。同样的,对其他符号也是如此。但是需要注意,对于一般的函数,确实好分析,但是大多存在一些级数和LOG的情况,这就要从定义出发进行论证了

记号含义通俗理解
(1)Θ(西塔)紧确界。相当于”=”
(2)O (大欧)上界。相当于”<=”
(3)o(小欧)非紧的上界。相当于”<”
(4)Ω(大欧米伽)下界。相当于”>=”
(5)ω(小欧米伽)非紧的下界。相当于”>”

问:为什么含有常数倍数C可以代表它的上界呢?

答:因为在趋于无穷的时候,倍数C的影响相对于n的影响微乎及微

问:为什么使用O(n)而不用Ω(n)呢?

答:因为我们分析最差情况,Ω(n)是渐进下界,并不能说明算法的最坏复杂度,所以没意义。

5、有关函数渐近的界的定理

(1)定理1

重要结论:可证明多项式函数的阶低于指数函数的阶

重要结论:对数函数的阶低于幂函数的阶

(2)定理2

(3)定理3

(4)小结

1、估计函数的阶的方法:

  • 计算极限
  • 阶具有传递性

2、对数函数的阶<幂函数的阶<指数函数的阶.

3、算法的时间复杂度是各步操作时间之和,在常数步的情况下取最高阶的函数即可.

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~