好网站建设公司北京,网站建设犭金手指a15,wordpress qi,互联网公司有国企吗一、前言在进一步学习数据结构与算法前#xff0c;我们应该先掌握算法分析的一般方法。算法分析主要包括对算法的时空复杂度进行分析#xff0c;但有些时候我们更关心算法的实际运行性能如何#xff0c;此外#xff0c;算法可视化是一项帮助我们理解算法实际执行过程的实用… 一、前言在进一步学习数据结构与算法前我们应该先掌握算法分析的一般方法。算法分析主要包括对算法的时空复杂度进行分析但有些时候我们更关心算法的实际运行性能如何此外算法可视化是一项帮助我们理解算法实际执行过程的实用技能在分析一些比较抽象的算法时这项技能尤为实用。在本篇博文中我们首先会介绍如何通过设计实验来量化算法的实际运行性能然后会介绍算法的时间复杂度的分析方法我们还会介绍能够非常便捷的预测算法性能的倍率实验。当然在文章的末尾我们会一起来做几道一线互联网的相关面试/笔试题来巩固所学达到学以致用。二、算法分析的一般方法1、量化算法的实际运行性能在介绍算法的时空复杂度分析方法前我们先来介绍以下如何来量化算法的实际运行性能这里我们选取的衡量算法性能的量化指标是它的实际运行时间。通常这个运行时间与算法要解决的问题规模相关比如排序100万个数的时间通常要比排序10万个数的时间要长。所以我们在观察算法的运行时间时还要同时考虑它所解决问题的规模观察随着问题规模的增长算法的实际运行时间时怎样增长的。这里我们采用算法第4版 (豆瓣)一书中的例子代码如下public class ThreeSum { public static int count(int[] a) { int N a.length; int cnt 0; for (int i 0; i N; i) { for (int j i 1; j N; j) { for (int k j 1; k N; k) { if (a[i] a[j] a[k] 0) { cnt; } } } } return cnt; } public static void main(String[] args) { int[] a StdIn.readAllInts(); StdOut.println(count(a)); }
}以上代码用到的StdIn和StdOut这两个类都在这里https://github.com/absfree/Algo。我们可以看到以上代码的功能是统计标准一个int[]数组中的所有和为0的三整数元组的数量。采用的算法十分直接就是从头开始遍历数组每次取三个数若和为0则计数加一最后返回的计数值即为和为0的三元组的数量。这里我们采取含有整数数量分别为1000、2000、4000的3个文件这些文件可以在上面的项目地址中找到来对以上算法进行测试观察它的运行时间随着问题规模的增长是怎样变化的。测量一个过程的运行时间的一个直接的方法就是在这个过程运行前后各获取一次当前时间两者的差值即为这个过程的运行时间。当我们的过程本身需要的执行时间很短时间这个测量方法可能会存在一些误差但是我们可以通过执行多次这个过程再取平均数来减小以至可以忽略这个误差。下面我们来实际测量一下以上算法的运行时间相关代码如下public static void main(String[] args) { int[] a In.readInts(args[0]); long startTime System.currentTimeMillis(); int count count(a); long endTime System.currentTimeMillis(); double time (endTime - startTime) / 1000.0; StdOut.println(The result is: count , and takes time seconds.); } 我们分别以1000、2000、4000个整数作为输入得到的运行结果如下The result is: 70, and takes 1.017 seconds. //1000个整数 The result is: 528, and takes 7.894 seconds. //2000个整数 The result is: 4039, and takes 64.348 seconds. //4000个整数我们从以上结果大概可你看到当问题的规模变为原来的2倍时实际运行时间大约变为原来的8倍。根据这个现象我们可以做出一个猜想程序的运行时间关于问题规模N的函数关系式为T(N) k*(n^3).在这个关系式中当n变为原来的2倍时T(N)会变为原来的8倍。那么ThreeSum算法的运行时间与问题规模是否满足以上的函数关系呢在介绍算法时间复杂度的相关内容后我们会回过头来再看这个问题。2、算法的时间复杂度分析1基本概念关于算法的时间复杂度这里我们先简单介绍下相关的三种符号记法第一种叫Big O notation它给出了运行时间的”渐进上界“也就是算法在最坏情况下运行时间的上限。它的定义如下对于f(n)和g(n)若存在常数c和N0使得对于所有n N0都有 |f(n)| c * g(n)则称f(n)为O(g(n)。第三种叫做Big Ω notation它给出了运行时间的“渐进下界”也就是算法在最坏情况下运行时间的下限。它的定义如下对于f(n)和g(n)若存在常数c和N0使得对于所有n N0都有|f(n)| c * g(n)则称f(n)为Ω(g(n))。第三种叫Big Θ notation它确定了运行时间的”渐进确界“。定义如下对于f(n)和g(n)若存在常数c和N0对于所有n N0都有|f(n)| c * g(n)则称f(n)为Θ为Θ(g(n))。我们在平常的算法分析中最常用到的是Big O notation。下面我们将介绍分析算法的时间复杂度的具体方法若对Big O notation的概念还不是很了解推荐大家看这篇文章http://blog.jobbole.com/55184/。2时间复杂度的分析方法这部分我们将以上面的ThreeSum程序为例来介绍一下算法时间复杂度的分析方法。为了方便阅读这里再贴一下上面的程序public static int count(int[] a) { int N a.length; int cnt 0; for (int i 0; i N; i) { for (int j i 1; j N; j) { for (int k j 1; k N; k) { if (a[i] a[j] a[k] 0) { cnt; } } } } return cnt; }在介绍时间复杂度分析方法前我们首先来明确下算法的运行时间究竟取决于什么。直观地想一个算法的运行时间也就是执行所有程序语句的耗时总和。然而在实际的分析中我们并不需要考虑所有程序语句的运行时间我们应该做的是集中注意力于最耗时的部分也就是执行频率最高而且最耗时的操作。也就是说在对一个程序的时间复杂度进行分析前我们要先确定这个程序中哪些语句的执行占用的它的大部分执行时间而那些尽管耗时大但只执行常数次和问题规模无关的操作我们可以忽略。我们选出一个最耗时的操作通过计算这些操作的执行次数来估计算法的时间复杂度下面我们来具体介绍这一过程。首先我们看到以上代码的第1行和第2行的语句只会执行一次因此我们可以忽略它们。然后我们看到第4行到第12行是一个三层循环最内存的循环体包含了一个if语句。也就是说这个if语句是以上代码中耗时最多的语句我们接下来只需要计算if语句的执行次数即可估计出这个算法的时间复杂度。以上算法中我们的问题规模为N输入数组包含的元素数目我们也可以看到if语句的执行次数与N是相关的。我们不难得出if语句会执行N * (N - 1) * (N - 2) / 6次因此这个算法的时间复杂度为O(n^3)。这也印证了我们之前猜想的运行时间与问题规模的函数关系T(n) k * n ^ 3。由此我们也可以知道算法的时间复杂度刻画的是随着问题规模的增长算法的运行时间的增长速度是怎样的。在平常的使用中Big O notation通常都不是严格表示最坏情况下算法的运行时间上限而是用来表示通常情况下算法的渐进性能的上限在使用Big O notation描述算法最坏情况下运行时间的上限时我们通常加上限定词“最坏情况“。通过以上分析我们知道分析算法的时间复杂度只需要两步比把大象放进冰箱还少一步) 寻找执行次数多的语句作为决定运行时间的[关键操作];分析关键操作的执行次数。在以上的例子中我们可以看到不论我们输入的整型数组是怎样的if语句的执行次数是不变的也就是说上面算法的运行时间与输入无关。而有些算法的实际运行时间高度依赖于我们给定的输入关于这一问题下面我们进行介绍。3、算法的期望运行时间算法的期望运行时间我们可以理解为在通常情况下算法的运行时间是多少。在很多时候我们更关心算法的期望运行时间而不是算法在最坏情况下运行时间的上限因为最坏情况和最好情况发生的概率是比较低的我们更常遇到的是一般情况。比如说尽管快速排序算法与归并排序算法的时间复杂度都为O(nlogn)但是在相同的问题规模下快速排序往往要比归并排序快因此快速排序算法的期望运行时间要比归并排序的期望时间小。然而在最坏情况下快速排序的时间复杂度会变为O(n^2)快速排序算法就是一个运行时间依赖于输入的算法对于这个问题我们可以通过打乱输入的待排序数组的顺序来避免发生最坏情况。4、倍率实验下面我们来介绍一下算法第4版 (豆瓣)一书中的“倍率实验”。这个方法能够简单有效地预测程序的性能并判断他们的运行时间大致的增长数量级。在正式介绍倍率实验前我们先来简单介绍下“增长数量级“这一概念同样引用自《算法》一书我们用~f(N)表示所有随着N的增大除以f(N)的结果趋于1的函数。用g(N)~f(N)表示g(N) / f(N)随着N的增大趋近于1。通常我们用到的近似方式都是g(N) ~ a * f(N)。我们将f(N)称为g(N)的增长数量级。我们还是拿ThreeSum程序来举例假设g(N)表示在输入数组尺寸为N时执行if语句的次数。根据以上的定义我们就可以得到g(N) ~ N ^ 3当N趋向于正无穷时g(N) / N^3 趋近于1。所以g(N)的增长数量级为N^3即ThreeSum算法的运行时间的增长数量级为N^3。现在我们来正式介绍倍率实验以下内容主要引用自上面提到的《算法》一书同时结合了一些个人理解。首先我们来一个热身的小程序public class DoublingTest { public static double timeTrial(int N) { int MAX 1000000; int[] a new int[N]; for (int i 0; i N; i) { a[i] StdRandom.uniform(-MAX, MAX); } long startTime System.currentTimeMillis(); int count ThreeSum.count(a); long endTime System.currentTimeMillis(); double time (endTime - startTime) / 1000.0; return time; } public static void main(String[] args) { for (int N 250; true; N N) { double time timeTrial(N); StdOut.printf(%7d %5.1f\n, N, time); } }
}以上代码会以250为起点每次讲ThreeSum的问题规模翻一倍并在每次运行ThreeSum后输出本次问题规模和对应的运行时间。运行以上程序得到的输出如下所示250 0.0 500 0.1 1000 0.6 2000 4.3 4000 30.6上面的输出之所以和理论值有所出入是因为实际运行环境是复杂多变的因而会产生许多偏差尽可能减小这种偏差的方式就是多次运行以上程序并取平均值。有了上面这个热身的小程序做铺垫接下来我们就可以正式介绍这个“可以简单有效地预测任意程序执行性能并判断其运行时间的大致增长数量级”的方法了实际上它的工作基于以上的DoublingTest程序大致过程如下开发一个[输入生成器]来产生实际情况下的各种可能的输入。反复运行下面的DoublingRatio程序直至time/prev的值趋近于极限2^b则该算法的增长数量级约为N^bb为常数。DoublingRatio程序如下运行倍率程序我们可以得到如下输出0.0 2.0 0.1 5.5 0.5 5.4 3.7 7.0 27.4 7.4 218.0 8.0我们可以看到time/prev确实收敛到了82^3)。那么为什么通过使输入不断翻倍而反复运行程序运行时间的比例会趋于一个常数呢答案是下面的[倍率定理]:若T(N) ~ a * N^b * lgN那么T(2N) / T(N) ~2^b。以上定理的证明很简单只需要计算T(2N) / T(N)在N趋向于正无穷时的极限即可。其中“a * N^b * lgN”基本上涵盖了常见算法的增长量级a、b为常数。值得我们注意的是当一个算法的增长量级为NlogN时对它进行倍率测试我们会得到它的运行时间的增长数量级约为N。实际上这并不矛盾因为我们并不能根据倍率实验的结果推测出算法符合某个特定的数学模型我们只能够大致预测相应算法的性能当N在16000到32000之间时14N与NlgN十分接近。5、均摊分析考虑下我们之前在 深入理解数据结构之链表 中提到的ResizingArrayStack也就是底层用数组实现的支持动态调整大小的栈。每次添加一个元素到栈中后我们都会判断当前元素是否填满的数组若是填满了则创建一个尺寸为原来两倍的新数组并把所有元素从原数组复制到新数组中。我们知道在数组未填满的情况下push操作的复杂度为O(1)而当一个push操作使得数组被填满创建新数组及复制这一工作会使得push操作的复杂度骤然上升到O(n)。对于上面那种情况我们显然不能说push的复杂度是O(n)我们通常认为push的“平均复杂度”为O(1)因为毕竟每n个push操作才会触发一次“复制元素到新数组”因而这n个push把这一代价一均摊对于这一系列push中的每个来说它们的均摊代价就是O(1)。这种记录所有操作的总成本并除以操作总数来讲成本均摊的方法叫做均摊分析也叫摊还分析。三、小试牛刀之实战名企面试题前面我们介绍了算法分析的一些姿势那么现在我们就来学以致用一起来解决几道一线互联网企业有关于算法分析的面试/笔试题。【腾讯】下面算法的时间复杂度是____int foo(int n) { if (n 1) { return 1 } return n * foo(n - 1);}看到这道题要我们分析算法时间复杂度后我们要做的第一步便是确定关键操作这里的关键操作显然是if语句那么我们只需要判断if语句执行的次数即可。首先我们看到这是一个递归过程foo会不断的调用自身直到foo的实参小于等于1foo就会返回1之后便不会再执行if语句了。由此我们可以知道if语句调用的次数为n次所以时间复杂度为O(n)。 【京东】以下函数的时间复杂度为____void recursive(int n, int m, int o) { if (n 0) { printf(%d, %d\n, m, o); } else { recursive(n - 1, m 1, o); recursive(n - 1, m, o 1); }}这道题明显要比上道题难一些那么让我们来按部就班的解决它。首先它的关键操作时if语句因此我们只需判断出if语句的执行次数即可。以上函数会在n 0的时候不断递归调用自身我们要做的是判断在到达递归的base case即n 0前共执行了多少次if语句。我们假设if语句的执行次数为T(n, m, o)那么我们可以进一步得到T(n, m, o) T(n-1, m1, o) T(n-1, m, o1) 当n 0时。我们可以看到base case与参数m, o无关因此我们可以把以上表达式进一步简化为T(n) 2T(n-1)由此我们可得T(n) 2T(n-1) (2^2) * T(n-2)......所以我们可以得到以上算法的时间复杂度为O(2^n)。 【京东】如下程序的时间复杂度为____其中m 1e 0x m;y 1;while (x - y e) { x (x y) / 2; y m / x;}print(x);以上算法的关键操作即while语句中的两条赋值语句我们只需要计算这两条语句的执行次数即可。我们可以看到当x - y e时while语句体内的语句就会执行x (x y) / 2使得x不断变小当yx时执行一次这个语句会使x变为约原来的一半假定y的值固定在1那么循环体的执行次数即为~logm而实际情况是y在每次循环体最后都会被赋值为m / x这个值总是比y在上一轮循环中的值大这样一来x-y的值就会更小所以以上算法的时间复杂度为O(logm)。 【搜狗】假设某算法的计算时间可用递推关系式T(n) 2T(n/2) nT(1) 1表示则该算法的时间复杂度为____根据题目给的递推关系式我们可以进一步得到T(n) 2(2T(n/4) n/2) n ... 将递推式进一步展开我们可以得到该算法的时间复杂度为O(nlogn)这里就不贴上详细过程了。 四、参考资料算法第4版 (豆瓣)来自absfree - 博客园链接www.cnblogs.com/absfree/p/5464779.html文章版权归原作者所有转载仅供学习使用不用于任何商业用途如有侵权请留言联系删除感谢合作。
