当前位置：新励学网 > 秒知问答 > 判断算法时间和空间效率的标准是

判断算法时间和空间效率的标准是

发表时间：2024-07-31 22:18:56 来源：网友投稿

编程实现算法后，算法就是由一组语句构成，算法的执行效率就由各语句执行的次数所决定。

一个算法花费的时间与算法中语句的执行次数成正比，哪个算法语句执行次数多，它花费的时间就多，把时间复杂度记为 T(n) ，一般情况下，算法的基本操作重复执行的次数是关于模块 n 的一个函数 f(n) ，所以我们可以把算法的时间复杂度记做： T(n) = O(f(n)) 。随着模块 n 的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。我们研究复杂度的目的是要比较两个算法的效率的高低，并不需要仔细地分析这个算法比那个算法多几次运算那么清，所以我们采用渐近复杂度分析来比较算法的效率。我们在分析算法的时间复杂度时，一般都会规定各种输入情况得出最好情况下 T_{max}(n) 、最坏情况下 T_{min}(n) 和平均情况下 T_{avg}(n) 。

1. 求绝对值我们需要求一个整数的绝对值，在算法设计上，只需要输入的值为负数时，返回它的相反数，其他情况返回本身，代码如下：public static int abs(int a) {return a < 0 ? -a : a;}该代码中只有一条运算指令语句，时间复杂度为 O(1) 。

2. 数组求和已知一个整型数组，需要对数组内所有元素求和，如果只是通过遍历所有元素而不使用其他方法进行求和，可以使用如下代码实现：public static int sum(int[] a) {int s = 0;for (int i : a) {s += i;}return s;}由代码可知，如果输入数组的大小为 n ，执行语句中初始化赋值需要时间 O(1) ，循环语句中的赋值操作需要时间为 O(1)*n ，所以语句执行的时间为： O(1)+O(1)*n=O(n+1)=O(n) 。

3. 二分查找已知一个有序数组，需要在数组中找到某个元素的位置，我们可以通过二分法来实现，代码如下：public static int binarySearch(int[] a, int b) {int i, r = 0, l = a.length;while (r <= l) {

免责声明：本站发布的教育资讯（图片、视频和文字）以本站原创、转载和分享为主，文章观点不代表本网站立场。

如果本文侵犯了您的权益，请联系底部站长邮箱进行举报反馈，一经查实，我们将在第一时间处理，感谢您对本站的关注！