crm系统和erp的区别,seo怎样,做网站找那些公司,wordpress授权更新2.1 开场白
2.2 数据结构与算法之间的关系
在“数据结构”课程中#xff0c;就算谈到算法#xff0c;也是为了帮助理解好数据结构#xff0c;并不会详细谈及算法的方方面面。
2.3 两种算法的比较
2.4 算法的定义
算法是解决特定问题求解步骤的描述#xff0c;在计算机…2.1 开场白
2.2 数据结构与算法之间的关系
在“数据结构”课程中就算谈到算法也是为了帮助理解好数据结构并不会详细谈及算法的方方面面。
2.3 两种算法的比较
2.4 算法的定义
算法是解决特定问题求解步骤的描述在计算机中表现为指令的有限序列并且每条指令表示一个或多个操作。
现实世界中的问题千奇百怪算法当然也就千变万化没有通用的算法可以解决所有的问题。
算法定义中提到了指令指令能被人或机器等计算装置执行。它可以是计算机指令也可以是我们平时的语言文字。
2.5 算法的特性
算法具有五个基本特性输入、输出、有穷性、确定性和可行性。 2.5.1 输入输出
算法具有零个或多个输入
算法至少有一个或多个输出
2.5.2 有穷性
有穷性指算法在执行有限的步骤之后自动结束而不会出现无限循环并且每一个步骤在可接受的时间内完成。
2.5.3 确定性
确定性算法的每一步骤都具有确定的含义不会出现二义性。
算法在一定条件下只有一条执行路径相同的输入只能有唯一的输出结果。算法的每个步骤被精确定义而无歧义。
2.5.4 可行性
可行性算法的每一步都必须是可行的也就是说每一步都能够通过执行有限次数完成。
可行性意味着算法可以转换为程序上机运行并得到正确的结果。
2.6 算法设计的要求
算法不是唯一的尽管算法不唯一相对好的算法还是存在的。
那么什么才叫好的算法呢 2.6.1 正确性
正确性算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
但是算法的“正确”通常在用法上有很大的差别大体分为以下四个层次。
1算法程序没有语法错误。
2算法程序对于合法的输入数据能够产生满足要求的输出结果
3算法程序对于非法的输入数据能够得出满足规格说明的结果。
4算法程序对于精心选择的甚至刁难的测试数据都有满足要求的输出结果。
层次1要求最低但是仅仅没有语法错误实在谈不上是好算法
层次4是最困难的我们几乎不可能逐一验证所有的输入都得到正确的结果。
因此算法的正确性在大部分情况下都不可能用程序来证明而是用数学方法证明的。证明一个复杂算法在所有层次上都是正确的代价非常昂贵。所以一般情况下我们把层次3作为一个算法是否正确的标准。
2.6.2 可读性
可读性算法设计的另一目的是为了便于阅读、理解和交流。
2.6.3 健壮性
健壮性当输入数据不合法时算法也能做出相关处理而不是产生异常或莫名其妙的结果。
2.6.4 时间效率高和存储量低
时间效率指的是算法的执行时间对于同一个问题如果有多个算法能够解决执行时间短的算法效率高执行时间长的效率低。存储量需求指的是算法在执行过程中需要的最大存储空间主要指算法程序运行时所占用的内存或外部硬盘存储空间。设计算法应该尽量满足时间效率高和存储量低的需求。
综上好的算法应该具有正确性、可读性、健壮性、高效率和低存储量的特征。
2.7 算法效率的度量方法
2.7.1 事后统计方法
事后统计方法这种方法主要是通过设计好的测试程序和数据利用计算机计时器对不同算法编制的程序的运行时间进行比较从而确定算法效率的高低。
但这种方法显然是有很大缺陷的
必须依据算法事先编制好程序这通常需要花费大量的时间和精力。如果编制出来发现它根本是很糟糕的算法不是竹篮打水一场空吗时间的比较依赖计算机硬件和软件等环境因素有时会掩盖算法本身的优劣。要知道现在的一台四核处理器的计算机跟当年286、386、486等老爷爷辈的机器相比在处理算法的运算速度上是不能相提并论的而所用的操作系统、编译器、运行框架等软件的不同也可以影响它们的结果就算是同一台机器CPU使用率和内存占用情况不一样也会造成细微的差异。算法的测试数据设计困难并且程序的运行时间往往还与测试数据的规模有很大关系效率高的算法在小的测试数据面前往往得不到体现。比如10个数字的排序不管用什么算法差异几乎是零。而如果有一百万个随机数字排序那不同算法的差异就非常大了。那么我们为了比较算法到底用多少数据来测试这是很难判断的问题。
基于事后统计方法有这样那样的缺陷我们考虑不予采纳。
2.7.2 事前分析估算方法
事前分析估算方法在计算机程序编制前依据统计方法对算法进行估算。
一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素 一个程序的运行时间依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少。
不计那些循环索引的递增和循环终止条件、变量声明、打印结果等操作
最终在分析程序的运行时间时最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。
我们在分析一个算法的运行时间时重要的是把基本操作的数量与输入规模关联起来即基本操作的数量必须表示成输入规模的函数 随着n值的越来越大它们在时间效率上的差异也就越来越大
2.8 函数的渐近增长
函数的渐近增长给定两个函数f(n)和g(n)如果存在一个整数N使得对于所有的nNf(n)总是比g(n)大那么我们说f(n)的增长渐近快于g(n)。
可以忽略这些加法常数
与最高次项相乘的常数并不重要
最高次项的指数大的函数随着n的增长结果也会增长更快
判断一个算法的效率时函数中的常数和其他次要项常常可以忽略而更应该关注主项最高阶项的阶数
如果我们可以对比这几个算法的关键执行次数函数的渐近增长性基本就可以分析出某个算法随着n的增大它会越来越优于另一算法或者越来越差于另一算法。
2.9 算法时间复杂度
2.9.1 算法时间复杂度定义
在进行算法分析时语句总的执行次数T(n)是关于问题规模n的函数进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度也就是算法的时间量度记作T(n)O(f(n))。它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同称作算法的渐近时间复杂度简称为时间复杂度。其中f(n)是问题规模n的某个函数。
这样用大写O( )来体现算法时间复杂度的记法我们称之为大O记法。 一般情况下随着n的增大T(n)增长最慢的算法为最优算法。
2.9.2 推导大O阶方法
推导大O阶 1用常数1取代运行时间中的所有加法常数。
2在修改后的运行次数函数中只保留最高阶项。
3如果最高阶项存在且其系数不是1则去除与这个项相乘的系数。 得到的结果就是大O阶。
2.9.3 常数阶
这种与问题的大小n的大小无关执行时间恒定的算法我们称之为具有O(1)的时间复杂度又叫常数阶。
注意不管这个常数是多少我们都记作O(1)而不能是O(3)、O(12)等其他任何数字这是初学者常常犯的错误。
对于分支结构而言无论是真还是假执行的次数都是恒定的不会随着n的变大而发生变化所以单纯的分支结构不包含在循环结构中其时间复杂度也是O(1)。
2.9.4 线性阶
线性阶的循环结构会复杂很多。要确定某个算法的阶次我们常常需要确定某个特定语句或某个语句集运行的次数。因此我们要分析算法的复杂度关键就是要分析循环结构的运行情况。
下面这段代码它的循环的时间复杂度为O(n)因为循环体中的代码须要执行n次。 int i;
for (i 0; i n; i)
{ /* 时间复杂度为O(1)的程序步骤序列 */
}
2.9.5 对数阶
int count 1;
while (count n)
{ count count * 2; /* 时间复杂度为O(1)的程序步骤序列 */
}
由于每次count乘以2之后就距离n更近了一分。也就是说有多少个2相乘后大于n则会退出循环。由2xn得到xlog2n。所以这个循环的时间复杂度为O(logn)。
2.9.6 平方阶
int i, j;
for (i 0; i n; i)
{ for (j 0; j n; j) { /* 时间复杂度为O(1)的程序步骤序列 */ }
}
这段代码的时间复杂度为O(n2)。
如果外循环的循环次数改为了m时间复杂度就变为O(m×n)。
循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。
int i, j;
for (i 0; i n; i)
{ /* 注意j i 而不是0 */ for (j i; j n; j) { /* 时间复杂度为O(1)的程序步骤序列 */ }
}
由于当i0时内循环执行了n次当i1时执行了n-1次……当in-1时执行了1次。所以总的执行次数为 用我们推导大O阶的方法第一条没有加法常数不予考虑第二条只保留最高阶项因此保留n2/2第三条去除这个项相乘的常数也就是去除1/2最终这段代码的时间复杂度为O(n2)。
理解大O推导不算难难的是对数列的一些相关运算这更多的是考察你的数学知识和能力
int i, j;
for (i 0; i n; i)
{ function(i);
}
void function(int count)
{ print(count);
} 函数体是打印count这个参数。其实这很好理解function函数的时间复杂度是O(1)。所以整体的时间复杂度为O(n)。
void function(int count)
{ int j;for (j count; j n; j) { /* 时间复杂度为O(1)的程序步骤序列 */ }
} 事实上这和刚才举的例子是一样的只不过把嵌套内循环放到了函数中所以最终的时间复杂度为O(n2)。
n; /* 执行次数为1 */
function(n); /* 执行次数为n */
int i, j;
for (i 0; i n; i) /* 执行次数为n2*/
{ function (i);
}
for (i 0; i n; i) /* 执行次数为n(n 1)/2 */
{ for (j i; j n; j) { /* 时间复杂度为O(1)的程序步骤序列 */ }
}
它的执行次数f(n)1nn2n(n1)/23/2·n23/2·n1根据推导大O阶的方法最终这段代码的时间复杂度也是O(n2)。
2.10 常见的时间复杂度
常见的时间复杂度 常用的时间复杂度所耗费的时间从小到大依次是 而像O(n3)过大的n都会使得结果变得不现实。同样指数阶O(2 n)和阶乘阶O(n!)等除非是很小的n值否则哪怕n只是100都是噩梦般的运行时间。所以这种不切实际的算法时间复杂度一般我们都不去讨论它。
2.11 最坏情况与平均情况
最坏情况运行时间是一种保证那就是运行时间将不会再坏了。在应用中这是一种最重要的需求通常除非特别指定我们提到的运行时间都是最坏情况的运行时间。
而平均运行时间也就是从概率的角度看这个数字在每一个位置的可能性是相同的所以平均的查找时间为n/2次后发现这个目标元素。
平均运行时间是所有情况中最有意义的因为它是期望的运行时间。
可现实中平均运行时间很难通过分析得到一般都是通过运行一定数量的实验数据后估算出来的。
对算法的分析一种方法是计算所有情况的平均值这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下都是指最坏时间复杂度。
2.12 算法空间复杂度
这是以存储空间来换取计算时间的小技巧。到底哪一个好其实要看你用在什么地方。
算法的空间复杂度通过计算算法所需的存储空间实现算法空间复杂度的计算公式记作S(n)O(f(n))其中n为问题的规模f(n)为语句关于n所占存储空间的函数。
一般情况下一个程序在机器上执行时除了需要存储程序本身的指令、常数、变量和输入数据外还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身和算法无关这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数则称此算法为原地工作空间复杂度为O(1)。
通常我们都使用“时间复杂度”来指运行时间的需求使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时通常都是指时间复杂度。
2.13 总结回顾
2.14 结尾语
