算法分析概念前面我们已经介绍了研究算法的最终目的就是如何花更少的时间如何占用更少的内存去完成相同的需求有关算法时间耗费分析我们称之为算法的时间复杂度分析有关算法的空间耗费分析我们称之为算法的空间复杂度分析。估算方法事后分析估算方法事前分析估算方法事后分析估算方法比较容易想到的方法就是我们把算法执行若干次然后拿个计时器在旁边计时这种事后统计的方法看上去的确不错并且也并非要我们真的拿个计算器在旁边计算因为计算机都提供了计时的功能。这种统计方法主要是通过设计好的测试程序和测试数据利用计算机计时器对不同的算法编制的程序的运行时间进行比较从而确定算法效率的高低但是这种方法有很大的缺陷必须依据算法实现编制好的测试程序通常要花费大量时间和精力测试完了如果发现测试的是非常糟糕的算法那么之前所做的事情就全部白费了。并且不同的测试环境(硬件环境)的差别导致测试的结果差异也很大。事前分析估算方法在计算机程序编写前依据统计方法对算法进行估算经过总结我们发现一个高级语言编写的程序程序在计算机上运行所消耗的时间取决于下列因素算法采用的策略和方案编译产生的代码质量问题的输入规模(所谓的问题输入规模就是输入量的多少)机器执行指令的速度由此可见抛开这些与计算机硬件、软件有关的因素一个程序的运行时间依赖于算法的好坏和问题的输入规模。如果算法固定那么该算法的执行时间就只和问题的输入规模有关系了。算法估算原则在研究算法的效率时我们只考虑核心代码的执行次数这样可以简化分析我们研究算法复杂度侧重的是当输入规模不断增大时算法的增长量的一个抽象(规律)而不是精确地定位需要执行多少次。我们分析一个算法的运行时间最重要的就是把核心操作的次数和输入规模关联起来。我们不关心编写程序所用的语言是什么也不关心这些程序将跑在什么样的计算机上我们只关心它所实现的算法。这样不计那些循环索引的递增和循环终止的条件、变量声明、打印结果等操作最终在分析程序的运行时间时最重要的是把程序看做是独立于程序设计语言的算法或一系列步骤。我们分析一个算法的运行时间最重要的就是把核心操作的次数和输入规模关联起来。常数时间操作函数渐近增长概念给定两个函数f(n)和g(n),如果存在一个整数N使得对于所有的nN,f(n)总是比g(n)大那么我们说f(n)的增长渐近快于g(n)。测试一随着输入规模的增大算法的常数操作可以忽略不计测试二随着输入规模的增大与最高次项相乘的常数可以忽略测试三最高次项的指数大的随着n的增长结果也会变得增长特别快测试四算法函数中n最高次幂越小算法效率越高小结算法函数中的常数可以忽略算法函数中最高次幂的常数因子可以忽略算法函数中最高次幂越小算法效率越高。算法时间复杂度 —大O记法定义在进行算法分析时语句总的执行次数T(n)是关于问题规模n的函数进而分析T(n)随着n的变化情况并确定T(n)的量级。算法的时间复杂度就是算法的时间量度记作:T(n)O(f(n))。它表示随着问题规模n的增大算法执行时间的增长率和f(n)的增长率相同称作算法的渐近时间复杂度简称时间复杂度其中f(n)是问题规模n的某个函数。在这里我们需要明确一个事情执行次数执行时间用大写O()来体现算法时间复杂度的记法我们称之为大O记法。一般情况下随着输入规模n的增大T(n)增长最慢的算法为最优算法。大O表示法—案例算法一算法二算法三如果忽略判断条件的执行次数和输出语句的执行次数那么当输入规模为n时以上算法执行的次数分别为算法一3次算法二n3次算法三n^22次所以上述算法的大O记法分别为算法一O(1)算法二O(n)算法三O(n^2)大O阶的表示法规则基于我们对函数渐近增长的分析推导大O阶的表示法有以下几个规则可以使用用常数1取代运行时间中的所有加法常数在修改后的运行次数中只保留高阶项如果最高阶项存在且常数因子不为1则去除与这个项相乘的常数常见的大O阶线性阶平方阶立方阶对数阶常数阶常见时间复杂度的一个小结他们的复杂程度从低到高依次为O(1)O(logn)O(n)O(nlogn)O(n^2) O(n^3)根据前面的折线图分析我们会发现从平方阶开始随着输入规模的增大时间成本会急剧增大所以我们的算法尽可能的追求的是O(1),O(logn),O(n),O(nlogn)这几种时间复杂度而如果发现算法的时间复杂度为平方阶、立方阶或者更复杂的那我们可以分为这种算法是不可取的需要优化。函数调用的时间复杂度分析案例一publicstaticvoidmain(String[]args){intn100;for(inti0;in;i){show(i);}}privatestaticvoidshow(inti){System.out.println(i);}在main方法中有一个for循环循环体调用了show方法由于show方法内部只执行了一行代码所以show方法的时间复杂度为O(1),那main方法的时间复杂度就是O(n)时间复杂度就是O(n)案例二publicstaticvoidmain(String[]args){intn10;for(inti0;in;i){show(i);}}privatestaticvoidshow(inti){for(intj0;ji;j){System.out.println(j);}}分析:show方法总共执行10次每次调用show方法时,会输出(i-1)次System.out.println() 方法所以当总共为 n10时 ,f(10)1012345678955测试方法1程序中加入k来计数publicclassTest01{publicstaticvoidmain(String[]args){intk0;intn10;for(inti0;in;i){kshow(i,k);k;}System.out.println();System.out.println(总次数: k);}privatestaticintshow(inti,intK){for(intj0;ji;j){System.out.print(i-);K;}returnK;}}测试方法2数学推导当n10时,结果为50555在main方法中有一个for循环循环体调用了show方法由于show方法内部也有一个for循环所以show方法的时间复杂度为O(n),那main方法的时间复杂度为O(n^2)时间复杂度为O(n^2)案例三在main方法中show(n)这行代码内部执行的次数为n第一个for循环内调用了show方法所以其执行次数近似为n^2,第二个嵌套for循环内只执行了一行代码所以其执行次数为n^2,根据大O推导规则去掉n保留最高阶项并去掉最高阶项的常数因子2所以最终main方法的时间复杂度为O(n^2)时间复杂度为O(n^2)最坏情况:从心理学角度讲每个人对发生的事情都会有一个预期比如看到半杯水有人会说哇哦还有半杯水哦但也有人会说天哪只有半杯水了。一般人处于一种对未来失败的担忧而在预期的时候趋向做最坏的打算这样即使最糟糕的结果出现当事人也有了心理准备比较容易接受结果。假如最糟糕的结果并没有出现当事人会很快乐。算法分析也是类似假如有一个需求有一个存储了n个随机数字的数组请从中查找出指定的数字。最好情况查找的第一个数字就是期望的数字那么算法的时间复杂度为O(1)最坏情况查找的最后一个数字才是期望的数字那么算法的时间复杂度为O(n)平均情况任何数字查找的平均成本是O(n/2)最坏情况是一种保证在应用中这是一种最基本的保障即使在最坏情况下也能够正常提供服务所以除非特别指定我们提到的运行时间都指的是最坏情况下的运行时间。算法的空间复杂度背景:计算机的软硬件都经历了一个比较漫长的演变史作为为运算提供环境的内存更是如此从早些时候的512k,经历了1M2M4M…等发展到现在的8G甚至16G和32G所以早期算法在运行过程中对内存的占用情况也是一个经常需要考虑的问题。我么可以用算法的空间复杂度来描述算法对内存的占用。java中常见内存占用:1.基本数据类型2.计算机访问内存的方式都是一次一个字节3.一个引用机器地址需要8个字节表示例如 Date date new Date(),则date这个变量需要占用8个字节来表示4.创建一个对象创建一个对象比如new Date()除了Date对象内部存储的数据(例如年月日等信息)占用的内存该对象本身也有内存开销每个对象的自身开销是16个字节用来保存对象的头信息。5.一般内存的使用如果不够8个字节都会被自动填充为8字节6.java中数组java中数组被被限定为对象他们一般都会因为记录长度而需要额外的内存一个原始数据类型的数组一般需要24字节的头信息(16个自己的对象开销4字节用于保存长度以及4个填充字节)再加上保存值所需的内存。算法的空间复杂度:了解了java的内存最基本的机制就能够有效帮助我们估计大量程序的内存使用情况。算法的空间复杂度计算公式记作S(n)O(f(n)),其中n为输入规模f(n)为语句关于n所占存储空间的函数。案例:需求:对指定的数组元素进行反转并返回反转的内容解法一解法二忽略判断条件占用的内存我们得出的内存占用情况如下算法一不管传入的数组大小为多少始终额外申请448个字节空间复杂度为O(1),算法二44n244n28;空间复杂度为O(n)根据大O推导法则算法一的空间复杂度为O(1),算法二的空间复杂度为O(n),所以从空间占用的角度讲算法一要优于算法二。小结:由于java中有内存垃圾回收机制并且jvm对程序的内存占用也有优化例如即时编译我们无法精确的评估一个java程序的内存占用情况但是了解了java的基本内存占用使我们可以对java程序的内存占用情况进行估算。由于现在的计算机设备内存一般都比较大基本上个人计算机都是4G起步大的可以达到32G所以内存占用一般情况下并不是我们算法的瓶颈普通情况下直接说复杂度默认为算法的时间复杂度。如果你做的程序是嵌入式开发尤其是一些传感器设备上的内置程序由于这些设备的内存很小一般为几kb这个时候对算法的空间复杂度就有要求了但是一般做java开发的基本上都是服务器开发一般不存在这样的问题。