【数据结构其实真不难】算法分析

2024-06-30 16:05| 来源: 网络整理| 查看: 265

💂 个人主页: 陶然同学🤟 版权: 本文由【陶然同学】原创、在CSDN首发、需要转载请联系博主💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦💅 想寻找共同成长的小伙伴，请点击【Java全栈开发社区】

前言前面我们已经介绍了，研究算法的最终目的就是如何花更少的时间，如何占用更少的内存去完成相同的需求，并且也通过案例演示了不同算法之间时间耗费和空间耗费上的差异，但我们并不能将时间占用和空间占用量化，因此，接下来我们要学习有关算法时间耗费和算法空间耗费的描述和分析。有关算法时间耗费分析，我们称之为算法的时间复杂度分析，有关算法的空间耗费分析，我们称之为算法的空间复杂度分析。 1.算法的时间复杂度分析我们要计算算法时间耗费情况，首先我们得度量算法的执行时间，那么如何度量呢？事后分析估算方法：比较容易想到的方法就是我们把算法执行若干次，然后拿个计时器在旁边计时，这种事后统计的方法看上去的确不错，并且也并非要我们真的拿个计算器在旁边计算，因为计算机都提供了计时的功能。这种统计方法主要是通过设计好的测试程序和测试数据，利用计算机计时器对不同的算法编制的程序的运行时间进行比较，从而确定算法效率的高低，但是这种方法有很大的缺陷：必须依据算法实现编制好的测试程序，通常要花费大量时间和精力，测试完了如果发现测试的是非常糟糕的算法，那么之前所做的事情就全部白费了，并且不同的测试环境 ( 硬件环境 ) 的差别导致测试的结果差异也很大。 public static void main(String[] args) { long start = System.currentTimeMillis(); int sum = 0; int n=100; for (int i = 1; i 1 时，算法 E1 的执行次数远远小于算法 F1 的执行次数；所以算法 E1 总体上是由于算法 F1 的。通过折线图我们会看到，算法 F 系列随着 n 的增长会变得特块，算法 E 系列随着 n 的增长相比较算法 F 来说，变得比较慢，所以可以得出结论：最高次项的指数大的，随着 n 的增长，结果也会变得增长特别快测试四：假设五个算法的输入规模都是 n ：算法 G ： n^3; 算法 H: n^2; 算法 I ： n: 算法 J ： logn 算法 K: 那么上述算法，哪个效率更高呢？

通过观察数据表格和折线图，很容易可以得出结论：算法函数中 n 最高次幂越小，算法效率越高总上所述，在我们比较算法随着输入规模的增长量时，可以有以下规则： 1. 算法函数中的常数可以忽略； 2. 算法函数中最高次幂的常数因子可以忽略； 3. 算法函数中最高次幂越小，算法效率越高。 1.2算法时间复杂度 1.2.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 n=100;//执行1次 sum = (n+1)*n/2;//执行1次 System.out.println("sum="+sum); } 算法二： public static void main(String[] args) { int sum = 0;//执行1次 int n=100;//执行1次 for (int i = 1; i

【本文地址】

公司简介

联系我们