网站优化 保定,上海上市装修公司,哈尔滨优化seo外包公司,专业培训心得体会前面我们已经介绍了#xff0c;研究算法的最终目的是如何花费更少的时间#xff0c;如何占用更少的内存去完成相同的需求#xff0c;并且也通过案例演示了不同算法之间时间耗费和空间耗费上的差异#xff0c;但我们并不能将时间占用和空间占用量化。因此#xff0c;接下来…前面我们已经介绍了研究算法的最终目的是如何花费更少的时间如何占用更少的内存去完成相同的需求并且也通过案例演示了不同算法之间时间耗费和空间耗费上的差异但我们并不能将时间占用和空间占用量化。因此接下来我们要学习有关算法时间耗费和算法空间耗费的描述与分析。有关算法时间耗费分析我们称之为算法的时间复杂度分析。
1.时间复杂度分析方法
我们要计算算法耗费时间情况首先我们得度量算法的执行时间那么如何度量呢
1.1事后分析估算方法
比较容易想到的方法就是我们把算法执行若干次然后拿个计时器在旁边计时这种事后统计的方法看上去的确不错并且也并非要我们真的拿个计算器在旁边计算因为计算机都提供了计时的功能。这种统计方法主要是通过设计好的测试程序和测试数据利用计算机计时器对不同的算法编制的程序的运行时间进行比较从而确定算法效率的高低但是这种方法有很大的缺陷︰必须依据算法实现编制好的测试程序通常要花费大量时间和精力测试完了如果发现测试的是非常糟糕的算法那么之前所做的事情就全部白费了并且不同的测试环境(硬件环境)的差别导致测试的结果差异也很大。 如下例所示 public static void main(String[] args) {long start System.currentTimeMillis();int sum 0;int n 100;for (int i 1; i n; i) {sum i;}System.out.println(sumsum);long end System.currentTimeMillis();System.out.println(end-start);}
如何理解该方法的缺陷举例说明比如我们用来三天的时间写了一个测试某个确定算法的程序然后运行它测试这个算法的时间发现测试时间很长那在实际中这个算法肯定就不能使用啊那也就是说这个算法是不好的是有缺陷不能用的那么你写的这个测试程序也是不能用的也就是说你白花了三天时间。这就是一个极大的缺陷。
1.2事前分析估算方法
在计算机程序编写之前依据统计方法对算法进行估算经过总结我们发现一个高级语言编写的程序程序在计算机上运行消耗的时间取决于下列因素
算法采用的策略和方案编译产生的代码质量不可人为干预问题的输入规模所谓的问题输入规模就是输入量是多少机器执行指令的速度不可人为干预
由此可见抛开那些与计算机硬件、软件有关的因素一个程序的运行时间依赖于算法的好坏和问题的输入规模。如果算法固定那么该算法的执行时间就只和问题的输入规模有关系了。
2.案例说明
2.1案例一
题目计算1到100的和
方法一
//如果输入量n为1则需要计算1次//如果输入量n为1亿则需要计算1亿次
public static void main(String[] args) {int sum 0; //执行1次int n 100; //执行1次for (int i 1; i n; i) {//执行n1次sum i; //执行n次}System.out.println(sumsum);}
方法二 //如果输入量n为1则需要计算1次//如果输入量n为1亿则需要计算1亿次public static void main(String[] args) {int sum 0; //执行1次int n 100; //执行1次sum (n1)*n/2; //执行1次System.out.println(sumsum);}
分析
方法一当输入规模为n时方法一执行了11n1n2n3次
方法二当输入规模为n时方法二执行了1113次
定量具体分析来看很明显方法二的执行次数是要远少于方法一的。
下面我们来深入分析一次这两段代码
方法一这个算法求和的核心代码是那个for循环如果我们把这个for循环看成是一个整体不考虑什么判断条件啊什么次数啊只考虑这个循环里面的内容然后再忽略其他的一些简要的一次就执行的代码那么方法一的执行次数就简化为n次
方法二同样的道理我们简化那么简单的一次就行的代码语句重点关注算法的核心语句的执行次数那么方法二的执行次数就简化为1次
再对比一下两个方法运行时间的差距就是n与1的差距。
注意这里我们用了简化思维直接去抓取每个算法的核心部分并分析这个核心部分执行的次数
问题
为什么循环判断条件在方法一中执行了n1次看起来是个不小的数字但是可以忽略呢
答看2.2案例二
2.2案例二
题目计算100个1100个2100个3,,,,,,100个100的结果
public static void main(String[] args) {int sum 0;int n 100;for (int i 1; i n; i) {for (int j 1; j n ; j) {sumi;}}System.out.println(sumsum);}
上面这个例子中如果我们要精确的研究循环的条件执行了多少次是一件很麻烦的事情并且由于真正计算和的代码是内循环的循环体所以在研究算法的效率时我们只考虑核心代码的执行次数这样可以简化分析。
下面给出2.1中问题的四个答案可以酌情选择思考
答案1精确循环次数很麻烦
第一个for循环的条件判断执行了100次第二个for循环的条件判断执行了10000次但是请思考下面的几种情况如果有5层循环每层次数不一样让你求第4层循环的判断次数是不是很麻烦如果上题中n1234求第二层循环的判断次数是不是也很麻烦所以我们忽略循环的判断次数。
答案2只关心得到结果的最核心部分
上面的所有循环都是为了sumi 这句服务的并且这个算法的最核心部分也是sumi最后的结果也是由这一句得到的所以我们只关心这一句。
答案3当做整体看
因为你每执行一次sumi 这句那就比如执行了前面的for循环的条件判断啊这二者是一个整体的是密不可分的所以就忽略了for的条件判断只关心那一句
答案4老师讲的
我们研究算法复杂度侧重的是当输入规模不断增大时算法的增长量的一个抽象(规律)而不是精确地定位需要执行多少次因为如果是这样的话我们又得考虑回编译期优化等问题容易主次跌倒。 我们不关心编写程序所用的语言是什么也不关心这些程序将跑在什么样的计算机上我们只关心它所实现的算法。这样不计那些循环索引的递增和循环终止的条件、变量声明、打印结果等操作最终在分析程序的运行时间时最重要的是把程序看做是独立于程序设计语言的算法或一系列步骤。我们分析一个算法的运行时间最重要的就是把核心操作的次数和输入规模关联起来。 3.函数渐进增长
概念
给定两个函数f(n)和g(n)如果存在一个整数N使得对于所有的nN,f(n)总是比g(n)大那么我们说f(n)的增长渐近快于(gn)。概念似乎有点艰涩难懂那接下来我们做几个测试。
3.1测试1
假设四个算法的输入规模都是n
算法A1要做2n3次操作可以这么理解︰先执行n次循环执行完毕后再有一个n次循环最后有3次运算算法A2要做2n次操作算法B1要做3n1次操作可以这个理解∶先执行n次循环再执行一个n次循环再执行一个n次循环最后有1次运算算法B2要做3n次操作
那么上述算法哪一个更快一些呢? 通过数据表格比较算法A1和算法B1 ∶
当输入规模n1时A1需要执行5次B1需要执行4次所以A1的效率比B1的效率低当输入规模n2时A1需要执行7次B1需要执行7次所以A1的效率和B1的效率一样当输入规模n2时A1需要的执行次数一直比B1需要执行的次数少所以A1的效率比B1的效率高
所以我们可以得出结论︰ 当输入规模n2时算法A1的渐近增长小于算法B1的渐近增长
通过观察折线图我们发现随着输入规模的增大算法A1和算法A2逐渐重叠到一块算法B1和
算法B2逐渐重叠到一块所以我们得出结论︰ 随着输入规模的增大算法的常数操作可以忽略不计
3.2测试2
假设四个算法的输入规模都是n :
算法C1需要做4n8次操作算法C2需要做n次操作算法D1需要做2n^2次操作算法D2需要做n^2次操作
那么上述算法哪个更快一些? 通过数据表格对比算法C1和算法D1 :
当输入规模n3时算法C1执行次数多于算法D1因此算法C1效率低一些当输入规模n3时算法C1执行次数少于算法D1因此算法D2效率低一些所以总体上算法C1要优于算法D1
通过折线图对比对比算法C1和C2 随着输入规模的增大算法C1和算法C2几乎重叠
通过折线图对比算法C系列和算法D系列 随着输入规模的增大即使去除n^2前面的常数因子D系列的次数要远远高于C系列。
因此可以得出结论 随着输入规模的增大与最高次项相乘的常数可以忽略
3.3测试3
假设四个算法的输入规模都是n
算法E12n^23n1算法E2n^2算法F12n^33n1算法F2n^3
那么上述算法哪个更快一些?
通过数据表格对比算法E1和算法F1 :
当n1时算法E1和算法F1的执行次数一样当n1时算法E1的执行次数远远小于算法F1的执行次数所以算法E1总体上是由于算法F1的。
通过折线图我们会看到算法F系列随着n的增长会变得特块算法E系列随着n的增长相比较算法F
来说变得比较慢所以可以得出结论 最高次项的指数大的随着n的增长结果也会变得增长特别快
3.4测试4
假设五个算法的输入规模都是n
算法G n^3算法Hn^2算法In算法Jlogn算法K1
那么上述算法哪个效率更高呢? 通过观察数据表格和折线图很容易可以得出结论 算法函数中n最高次幂越小算法效率越高
3.5小结
总上所述在我们比较算法随着输入规模的增长量时可以有以下规则
算法函数中的常数可以忽略算法函数中最高次幂的常数因子可以忽略算法函数中是高次幂越小算法效率越高
4.大O计法
4.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)增长最慢的算法为最优算法。
4.2案例分析
下面用大O表示法来表示一些求和算法的时间复杂度
算法一 public static void main(String[] args) {int sum 0;//执行1次int n 100;//执行1次sum (n1)*n/2;//执行1次System.out.println(sumsum);}
算法二 public static void main(String[] args) {int sum 0;//执行1次int n 100;//执行1次for (int i 1; i n; i) {sumi;//执行n次}System.out.println(sumsum);}
算法三 public static void main(String[] args) {int sum 0;//执行1次int n 100;//执行1次for (int i 1; i n; i) {for (int j 1; j n ; j) {sumi;//执行n^2次}}System.out.println(sumsum);}
如果忽略判断条件的执行次数和输出语句的执行次数那么当输入规模为n时以上算法执行的次
数分别为
算法一3次
算法二n3次
算法三n^22次
如果用大o记法表示上述每个算法的时间复杂度应该如何表示呢基于我们对函数渐近增长的分
析推导大O阶的表示法有以下几个规则可以使用
用常数1取代运行时间中的所有加法常数在修改后的运行次数中只保留高阶项如果最高阶项存在且常数因子不为1则去除与这个项相乘的常数
所以上述算法的大O计法分别为 算法一O(1) 算法二O(n) 算法三O(n^2)
5.小结
这篇文章首先我们给出了算法的时间复杂度的分析方法引导我们如何去分析一个算法的时间复杂度然后讲了一系列的函数渐进增长通过具体的实例总结了一些结论最后我们在这些结论的基础上提出来大O计法然后结合大O计法和那些结论我们实际的分析了一些求和算法的时间复杂度。
