时间复杂度的天差地别？这个实验带你直观感受

时间复杂度的天差地别？这个实验带你直观感受

我们都说时间复杂度很重要，却无法直接感受到时间复杂度的重要性。那么这次实验就带你直观感受到不同算法之间时间复杂度的巨大差距

实验原理： 在这个实验中，我们需要用到System.currentTimeMillis()。 System.currentTimeMillis()的作用是可以获得当前时间，那么在执行算法之前获取当前时间，在执行算法之后我们再获得当前时间，前后两次当前时间相减，就可以得到执行算法的时间。

在这次实验中，我们比较两种算法：二分查找和顺序查找的时间复杂度。 这两种查找都是在一个数组中找到我们要的元素，然后返回该元素的小标

//顺序查找 private static int search(int[] arr,int key) {//arr是数组，key是目标元素 for(int i=0;i

//二分查找 private static int binarySearch(int []arr,int low,int high,int key) {//arr是数组，low是0，high是数组下表的最大值，key是目标元素 if(low>high) { return -1; } int mid=(low+high)/2; if(arr[mid]key) { return binarySearch(arr,low,mid-1,key); } else { return mid; } }

接下来上完整实验代码

public class Main { public static void main(String[] args) { // TODO Auto-generated method stub int [] x =new int [10000*10000]; for(int i=0;ihigh) { return -1; } int mid=(low+high)/2; if(arr[mid]key) { return binarySearch(arr,low,mid-1,key); } else { return mid; } }}

可以看到，二分查找执行的时间为0ms，说明时间复杂度很小，

而顺序查找执行时间为32ms，时间复杂度很大，这两者差距可以说是无穷大。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。