二分法及原始算法查找效率 浅谈二分法查找和原始算法查找的效率对比
after95 人气:0想了解浅谈二分法查找和原始算法查找的效率对比的相关内容吗,after95在本文为您仔细讲解二分法及原始算法查找效率的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:二分法查找,原始算法查找,下面大家一起来学习吧。
我就废话不多说了,大家还是直接看代码吧!
import java.text.MessageFormat; public class AppTest { static int length = 70000000; static int[] array = new int[length]; static { for (int i = 0; i < length; i++) { array[i] = i; } } public static void main(String[] args) { for (int i = 0; i < 10; i++) { int target = (int) (Math.random() * length * 2); long start_f1 = System.currentTimeMillis(); int index_f1 = findIndex(array, target); long end_f1 = System.currentTimeMillis(); long time_f1 = end_f1 - start_f1; long start_f2 = System.currentTimeMillis(); int index_f2 = findIndexByFor(array, target); long end_f2 = System.currentTimeMillis(); long time_f2 = end_f2 - start_f2; System.out.println(MessageFormat.format("目标数据:{0}\t二分法耗时:{1}\t普通方法耗时:{2}\t二分法结果:{3}\t普通方法结果:{4}", target, time_f1, time_f2, index_f1, index_f2)); } } public static int findIndex(int[] arr, int target) { return findIndex(arr, 0, arr.length, target); } public static int findIndex(int[] arr, int start, int end, int target) { int middle = (start + end) / 2; if (target == arr[middle]) { return middle; } else if (start > end || target < arr[0] || target > arr[arr.length - 1]) { return -1; } else if (target < arr[middle]) { return findIndex(arr, start, middle - 1, target); } else if (target > arr[middle]) { return findIndex(arr, middle + 1, end, target); } return -1; } public static int findIndexByFor(int[] arr, int target) { int index = 0; for (int i : arr) { if (i == target) { return index; } index++; } return -1; } }
查找结果:
总结:
总结过我们可以看出,二分法查找几乎是不耗时,所以方法是很重要的
补充知识:顺序查找与二分查找时间复杂度的比较
注意要点:通过System.currentTimeMills();来获取当前时间,来计算该算法运行运算时间 顺序查找的时间复杂度为O(n)
二分查找的时间复杂度为O(log(n))
但两者的运行时间的结果却千差万别,可知当计算量很大的情况下算法优化的必要性。
import java.util.Arrays; public class Main { public static int a[] = new int[10000*10000]; public static void main(String[] args) { for(int i = 0; i < 10000* 10000; i ++) { a[i] = i + 1; } int target = 10000 * 10000; //计算顺序查找所用时间 long start = System.currentTimeMillis(); find(target); long end = System.currentTimeMillis(); System.out.println(end - start + "ms"); //计算二分查找所用时间 start = System.currentTimeMillis(); Arrays.binarySearch(a, target); end = System.currentTimeMillis(); System.out.println(end - start + "ms"); } private static void find(int target) { for(int i = 0; i < 10000 * 10000; i ++) { if(a[i] == target) { return; } } } }
运行结果:
55ms
0ms
以上这篇浅谈二分法查找和原始算法查找的效率对比就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持。
加载全部内容