安徽省建设厅质量监督站网站,wordpress保护后台登录,自己如何做一个网络平台,网站集约化建设进度报告02_算法分析 0.1 算法的时间复杂度分析0.1.1 函数渐近增长概念#xff1a;输入规模n2时#xff0c;算法A1的渐近增长小于算法B1 的渐近增长随着输入规模的增大#xff0c;算法的常数操作可以忽略不计测试二#xff1a;随着输入规模的增大#xff0c;与最高次项相乘的常… 02_算法分析 0.1 算法的时间复杂度分析0.1.1 函数渐近增长概念输入规模n2时算法A1的渐近增长小于算法B1 的渐近增长随着输入规模的增大算法的常数操作可以忽略不计测试二随着输入规模的增大与最高次项相乘的常数可以忽略最高次项的指数大的随着n的增长结果也会变得增长特别快1 算法函数中的常数可以忽略 1.1 算法时间复杂度1.1.1 大O记法定义2 用常数1取代运行时间中的所有加法常数 2.1 常见的大O阶3 线性阶4 平方阶5 立方阶6 对数阶7 常数阶 7.1 函数调用的时间复杂度分析案例二案例三 7.1.1 最坏情况最好情况 7.2 算法的空间复杂度分析7.2.1 java中常见内存占用7.2.2 算法的空间复杂度 一、算法分析
前面我们已经介绍了研究算法的最终目的就是如何花更少的时间如何占用更少的内存去完成相同的需求并且 也通过案例演示了不同算法之间时间耗费和空间耗费上的差异但我们并不能将时间占用和空间占用量化因此 接下来我们要学习有关算法时间耗费和算法空间耗费的描述和分析。有关算法时间耗费分析我们称之为算法的时 间复杂度分析有关算法的空间耗费分析我们称之为算法的空间复杂度分析。
0.1 算法的时间复杂度分析
我们要计算算法时间耗费情况首先我们得度量算法的执行时间那么如何度量呢 事后分析估算方法比较容易想到的方法就是我们把算法执行若干次然后拿个计时器在旁边计时这种事后统计的方法看上去的确不 错并且也并非要我们真的拿个计算器在旁边计算因为计算机都提供了计时的功能。这种统计方法主要是通过设 计好的测试程序和测试数据利用计算机计时器对不同的算法编制的程序的运行时间进行比较从而确定算法效率 的高低但是这种方法有很大的缺陷必须依据算法实现编制好的测试程序通常要花费大量时间和精力测试完 了如果发现测试的是非常糟糕的算法那么之前所做的事情就全部白费了并且不同的测试环境(硬件环境)的差别 导致测试的结果差异也很大。
public static void main(String[] args) {long start System.currentTimeMillis();int sum 0;int n100;for (int i 1; i n; i) { sum i;}System.out.println(sum sum);long end System.currentTimeMillis(); System.out.println(end-start);
}事前分析估算方法在计算机程序编写前依据统计方法对算法进行估算经过总结我们发现一个高级语言编写的程序程序在计算机 上运行所消耗的时间取决于下列因素
算法采用的策略和方案编译产生的代码质量问题的输入规模(所谓的问题输入规模就是输入量的多少)机器执行指令的速度
此可见抛开这些与计算机硬件、软件有关的因素一个程序的运行时间依赖于算法的好坏和问题的输入规模。 如果算法固定那么该算法的执行时间就只和问题的输入规模有关系了。我么再次以之前的求和案例为例进行分析。需求计算1到100的和。第一种解法
如果输入量为n为1则需要计算1次如果输入量n为1亿则需要计算1亿次
public static void main(String[] args) {int sum 0;//执行1次int n100;//执行1次for (int i 1; i n; i) {//执行了n1次sum i;//执行了n次}System.out.println(sum sum); 10
}
第二种解法
如果输入量为n为1则需要计算1次如果输入量n为1亿则需要计算1次
public static void main(String[] args) {int sum 0;//执行1次int n100;//执行1次sum (n1)*n/2;//执行1次System.out.println(sumsum);
}因此当输入规模为n时第一种算法执行了11(n1)n2n3次第二种算法执行了1113次。如果我们把 第一种算法的循环体看做是一个整体忽略结束条件的判断那么其实这两个算法运行时间的差距就是n和1的差 距。为什么循环判断在算法1里执行了n1次看起来是个不小的数量但是却可以忽略呢我们来看下一个例子 需求计算100个1100个2100个3…100个100的结果代码
public static void main(String[] args) {int sum0;int n100;for (int i 1; i n ; i) {for (int j 1; j n ; j) {sumi;}}System.out.println(sumsum); }上面这个例子中如果我们要精确的研究循环的条件执行了多少次是一件很麻烦的事情并且由于真正计算和 的代码是内循环的循环体所以在研究算法的效率时我们只考虑核心代码的执行次数这样可以简化分析。我们研究算法复杂度侧重的是当输入规模不断增大时算法的增长量的一个抽象(规律)而不是精确地定位需要 执行多少次因为如果是这样的话我们又得考虑回编译期优化等问题容易主次跌倒。我们不关心编写程序所用的语言是什么也不关心这些程序将跑在什么样的计算机上我们只关心它所实现的算 法。这样不计那些循环索引的递增和循环终止的条件、变量声明、打印结果等操作最终在分析程序的运行时间 时最重要的是把程序看做是独立于程序设计语言的算法或一系列步骤。我们分析一个算法的运行时间最重要的 就是把核心操作的次数和输入规模关联起来。
0.1.1 函数渐近增长 概念
定两个函数f(n)和g(n),如果存在一个整数N使得对于所有的nN,f(n)总是比g(n)大那么我们说f(n)的增长渐近 快于g(n)。概念似乎有点艰涩难懂那接下来我们做几个测试。测试一假设四个算法的输入规模都是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逐渐重叠 到一块所以我们得出结论
随着输入规模的增大算法的常数操作可以忽略不计测试二
假设四个算法的输入规模都是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系列。
因此可以得出结论
随着输入规模的增大与最高次项相乘的常数可以忽略
测试三假设四个算法的输入规模都是n 算法E1:2n^23n1;算法E2n^2算法F12n^33n1 算法F2 n^3那么上述算法哪个更快一些 通过数据表格对比算法E1和算法F1当n1时算法E1和算法F1的执行次数一样当n1时算法E1的执行次数远远小于算法F1的执行次数 所以算法E1总体上是由于算法F1的。通过折线图我们会看到算法F系列随着n的增长会变得特块算法E系列随着n的增长相比较算法F来说变得比较 慢所以可以得出结论
最高次项的指数大的随着n的增长结果也会变得增长特别快
测试四假设五个算法的输入规模都是n 算法Gn^3;算法H:n^2;算法In:算法Jlogn算法K:1那么上述算法哪个效率更高呢
通过观察数据表格和折线图很容易可以得出结论 算法函数中n最高次幂越小算法效率越高总上所述在我们比较算法随着输入规模的增长量时可以有以下规则
1 算法函数中的常数可以忽略
算法函数中最高次幂的常数因子可以忽略算法函数中最高次幂越小算法效率越高。 1.1 算法时间复杂度 1.1.1 大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表示法来表示一些求和算法的时间复杂度 算法一
public static void main(String[] args) {int sum 0;//执行1次int n100;//执行1次sum (n1)*n/2;//执行1次System.out.println(sumsum);
}算法二
public static void main(String[] args) {int sum 0;//执行1次int n100;//执行1次for (int i 1; i n; i) {sum i;//执行了n次6 }System.out.println(sum sum); }
}
算法三 public static void main(String[] args) {int sum0;//执行1次int n100;//执行1次for (int i 1; i n ; i) {for (int j 1; j n ; j) {sumi;//执行n^2次7 }}System.out.println(sumsum); }
}如果忽略判断条件的执行次数和输出语句的执行次数那么当输入规模为n时以上算法执行的次数分别为 算法一3次算法二n3次 算法三n^22次如果用大O记法表示上述每个算法的时间复杂度应该如何表示呢基于我们对函数渐近增长的分析推导大O阶 的表示法有以下几个规则可以使用
2 用常数1取代运行时间中的所有加法常数
在修改后的运行次数中只保留高阶项**如果最高阶项存在且常数因子不为1则去除与这个项相乘的常数 **所以上述算法的大O记法分别为
算法一O(1) 算法二O(n)
算法三O(n^2)
2.1 常见的大O阶 3 线性阶
一般含有非嵌套循环涉及线性阶线性阶就是随着输入规模的扩大对应计算次数呈直线增长例如 public static void main(String[] args) {int sum 0;int n100;for (int i 1; i n; i) {sum i;}System.out.println(sum sum);
}上面这段代码它的循环的时间复杂度为O(n),因为循环体中的代码需要执行n次
4 平方阶
一般嵌套循环属于这种时间复杂度
public static void main(String[] args) {int sum0,n100;for (int i 1; i n ; i) {for (int j 1; j n ; j) { sumi;}}System.out.println(sum);
}上面这段代码n100也就是说外层循环每执行一次内层循环就执行100次那总共程序想要从这两个循环 中出来就需要执行100*100次也就是n的平方次所以这段代码的时间复杂度是O(n^2).
5 立方阶
一般三层嵌套循环属于这种时间复杂度
public static void main(String[] args) {int x0,n100;for (int i 1; i n ; i) {for (int j i; j n ; j) {for (int j i; j n ; j) { x;}}}System.out.println(x);
}上面这段代码n100也就是说外层循环每执行一次中间循环循环就执行100次中间循环每执行一次最 内层循环需要执行100次那总共程序想要从这三个循环中出来就需要执行100_100_100次也就是n的立方所 以这段代码的时间复杂度是O(n^3).
6 对数阶
对数属于高中数学的内容我们分析程序以程序为主数学为辅所以不用过分担心。
1 int i1,n100;2 while(in){ 3 i i*2; 4 }
由于每次i*2之后就距离n更近一步假设有x个2相乘后大于n则会退出循环。由于是2^xn,得到xlog(2)n,所 以这个循环的时间复杂度为O(logn);对于对数阶由于随着输入规模n的增大不管底数为多少他们的增长趋势是一样的所以我们会忽略底数。 7 常数阶
一般不涉及循环操作的都是常数阶因为它不会随着n的增长而增加操作次数。例如 public static void main(String[] args) { int n100;int in2;System.out.println(i);
}上述代码不管输入规模n是多少都执行2次根据大O推导法则常数用1来替换所以上述代码的时间复杂度 为O(1)下面是对常见时间复杂度的一个总结
描述增长的数量级说明举例常数级别1普通语句将两个数相加对数级别logN二分策略二分查找线性级别N循环找出最大元素线型对数级别NlogN分治思想归并排序平方级别N^2双层循环检查所有元素对立方级别N^3三层循环检查所有三元组指数级别2^N穷举查找检查所有子集
他们的复杂程度从低到高依次为O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)根据前面的折线图分析我们会发现从平方阶开始随着输入规模的增大时间成本会急剧增大所以我们的 算法尽可能的追求的是O(1),O(logn),O(n),O(nlogn)这几种时间复杂度而如果发现算法的时间复杂度为平方阶、 立方阶或者更复杂的那我们可以分为这种算法是不可取的需要优化。
7.1 函数调用的时间复杂度分析
之前我们分析的都是单个函数内算法代码的时间复杂度接下来我们分析函数调用过程中时间复杂度。 案例一
public static void main(String[] args) {int n100;for (int i 0; i n; i) { show(i);}
}
priv0ate static void show(int i) {System.out.println(i);
}在main方法中有一个for循环循环体调用了show方法由于show方法内部只执行了一行代码所以show方法 的时间复杂度为O(1),那main方法的时间复杂度就是O(n)
案例二 public static void main(String[] args) {int n100;for (int i 0; i n; i) { show(i);}
}
private static void show(int i) {for (int j 0; j i; i) { System.out.println(i);}
}
在main方法中有一个for循环循环体调用了show方法由于show方法内部也有一个for循环所以show方法 的时间复杂度为O(n),那main方法的时间复杂度为O(n^2)
案例三
public static void main(String[] args) {int n100; show(n);for (int i 0; i n; i) { show(i);}for (int i 0; i n; i) {for (int j 0; j n; j) { System.out.println(j);}}
}
private static void show(int i) {for (int j 0; j i; i) { System.out.println(i);}
}在show方法中有一个for循环所以show方法的时间复杂度为O(n),在main方法中show(n)这行代码内部执行 的次数为n第一个for循环内调用了show方法所以其执行次数为n^2,第二个嵌套for循环内只执行了一行代码 所以其执行次数为n2,那么main方法总执行次数为nn2n22n2n。根据大O推导规则去掉n保留最高阶项并去掉最高阶项的常数因子2所以最终main方法的时间复杂度为O(n^2)
7.1.1 最坏情况
从心理学角度讲每个人对发生的事情都会有一个预期比如看到半杯水有人会说哇哦还有半杯水哦但也 有人会说天哪只有半杯水了。一般人处于一种对未来失败的担忧而在预期的时候趋向做最坏的打算这样即 使最糟糕的结果出现当事人也有了心理准备比较容易接受结果。假如最糟糕的结果并没有出现当事人会很快 乐。算法分析也是类似假如有一个需求有一个存储了n个随机数字的数组请从中查找出指定的数字。
public int search(int num){int[] arr{11,10,8,9,7,22,23,0};for (int i 0; i arr.length; i) {if (numarr[i]){return i;}}return -1;
}最好情况
查找的第一个数字就是期望的数字那么算法的时间复杂度为O(1) 最坏情况查找的最后一个数字才是期望的数字那么算法的时间复杂度为O(n) 平均情况任何数字查找的平均成本是O(n/2)最坏情况是一种保证在应用中这是一种最基本的保障即使在最坏情况下也能够正常提供服务所以除非 特别指定我们提到的运行时间都指的是最坏情况下的运行时间。
7.2 算法的空间复杂度分析
计算机的软硬件都经历了一个比较漫长的演变史作为为运算提供环境的内存更是如此从早些时候的512k,经 历了1M2M4M…等发展到现在的8G甚至16G和32G所以早期算法在运行过程中对内存的占用情况也是 一个经常需要考虑的问题。我么可以用算法的空间复杂度来描述算法对内存的占用。
7.2.1 java中常见内存占用
基本数据类型内存占用情况
数据类型内存占用字节数byte1short2int4long8float4double8boolean1char2
计算机访问内存的方式都是一次一个字节 一个引用机器地址需要8个字节表示
例如 Date date new Date(),则date这个变量需要占用8个字节来表示
创建一个对象比如new Date()除了Date对象内部存储的数据(例如年月日等信息)占用的内存该对象本身也有内存开销每个对象的自身开销是16个字节用来保存对象的头信息。一般内存的使用如果不够8个字节都会被自动填充为8字节 java中数组被被限定为对象他们一般都会因为记录长度而需要额外的内存一个原始数据类型的数组一般需要
24字节的头信息(16个自己的对象开销4字节用于保存长度以及4个填充字节)再加上保存值所需的内存。
7.2.2 算法的空间复杂度
了解了java的内存最基本的机制就能够有效帮助我们估计大量程序的内存使用情况。算法的空间复杂度计算公式记作S(n)O(f(n)),其中n为输入规模f(n)为语句关于n所占存储空间的函数。 案例对指定的数组元素进行反转并返回反转的内容。解法一
public static int[] reverse1(int[] arr){int narr.length;//申请4个字节int temp;//申请4个字节for(int start0,endn-1;startend;start,end--){temparr[start];arr[start]arr[end];arr[end]temp; }return arr; 10
}解法二
public static int[] reverse2(int[] arr){int narr.length;//申请4个字节int[] tempnew int[n];//申请n*4个字节数组自身头信息开销24个字节for (int i n-1; i 0; i--) {temp[n-1-i]arr[i];}return temp;
}忽略判断条件占用的内存我们得出的内存占用情况如下 算法一不管传入的数组大小为多少始终额外申请448个字节 算法二44n244n28;根据大O推导法则算法一的空间复杂度为O(1),算法二的空间复杂度为O(n),所以从空间占用的角度讲算法一要 优于算法二。由于java中有内存垃圾回收机制并且jvm对程序的内存占用也有优化例如即时编译我们无法精确的评估一 个java程序的内存占用情况但是了解了java的基本内存占用使我们可以对java程序的内存占用情况进行估算。由于现在的计算机设备内存一般都比较大基本上个人计算机都是4G起步大的可以达到32G所以内存占用一般 情况下并不是我们算法的瓶颈普通情况下直接说复杂度默认为算法的时间复杂度。但是如果你做的程序是嵌入式开发尤其是一些传感器设备上的内置程序由于这些设备的内存很小一般为几kb这个时候对算法的空间复杂度就有要求了但是一般做java开发的基本上都是服务器开发一般不存在这样 的问题。
