欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

淺談二分法查找和原始算法查找的效率對(duì)比

 更新時(shí)間:2020年08月18日 09:39:36   作者:after95  
這篇文章主要介紹了淺談二分法查找和原始算法查找的效率對(duì)比,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧

我就廢話不多說(shuō)了,大家還是直接看代碼吧!

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("目標(biāo)數(shù)據(jù):{0}\t二分法耗時(shí):{1}\t普通方法耗時(shí):{2}\t二分法結(jié)果:{3}\t普通方法結(jié)果:{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;
 }
} 

查找結(jié)果:

總結(jié):

總結(jié)過(guò)我們可以看出,二分法查找?guī)缀跏遣缓臅r(shí),所以方法是很重要的

補(bǔ)充知識(shí):順序查找與二分查找時(shí)間復(fù)雜度的比較

注意要點(diǎn):通過(guò)System.currentTimeMills();來(lái)獲取當(dāng)前時(shí)間,來(lái)計(jì)算該算法運(yùn)行運(yùn)算時(shí)間 ​​​​​​​ 順序查找的時(shí)間復(fù)雜度為O(n)

二分查找的時(shí)間復(fù)雜度為O(log(n))

但兩者的運(yùn)行時(shí)間的結(jié)果卻千差萬(wàn)別,可知當(dāng)計(jì)算量很大的情況下算法優(yōu)化的必要性。

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;
//計(jì)算順序查找所用時(shí)間
		long start = System.currentTimeMillis();
		find(target);
		long end = System.currentTimeMillis();
		System.out.println(end - start + "ms");
//計(jì)算二分查找所用時(shí)間	
	 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;
			}
		}
	}
 
}

運(yùn)行結(jié)果:

55ms

0ms

以上這篇淺談二分法查找和原始算法查找的效率對(duì)比就是小編分享給大家的全部?jī)?nèi)容了,希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。

相關(guān)文章

  • idea pom導(dǎo)入net.sf.json的jar包失敗的解決方案

    idea pom導(dǎo)入net.sf.json的jar包失敗的解決方案

    JSON(JavaScript Object Notation,JS對(duì)象簡(jiǎn)譜)是一種輕量級(jí)的數(shù)據(jù)交換格式,這篇文章主要介紹了idea pom導(dǎo)入net.sf.json的jar包失敗的解決方案,感興趣的朋友一起看看吧
    2023-11-11
  • Spring Boot打war包的實(shí)例教程

    Spring Boot打war包的實(shí)例教程

    本篇文章主要介紹了Spring Boot打war包的實(shí)例教程,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2018-02-02
  • SpringBoot中Dozer的使用小結(jié)

    SpringBoot中Dozer的使用小結(jié)

    dozer是用來(lái)兩個(gè)對(duì)象之間屬性轉(zhuǎn)換的工具,有了這個(gè)工具之后,我們將一個(gè)對(duì)象的所有屬性值轉(zhuǎn)給另一個(gè)對(duì)象時(shí),就不需要再去寫重復(fù)的set和get方法了,下面介紹下SpringBoot中Dozer的使用,感興趣的朋友一起看看吧
    2022-03-03
  • Java8新特性之StampedLock_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理

    Java8新特性之StampedLock_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理

    本文從synchronized、Lock到Java8新增的StampedLock進(jìn)行對(duì)比分析,對(duì)Java8新特性之StampedLock相關(guān)知識(shí)感興趣的朋友一起看看吧
    2017-06-06
  • SpringBoot2學(xué)習(xí)之springboot與spring區(qū)別分析

    SpringBoot2學(xué)習(xí)之springboot與spring區(qū)別分析

    這篇文章主要為大家介紹了SpringBoot2學(xué)習(xí)之springboot與spring區(qū)別分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-05-05
  • 詳解Java中二叉樹的基礎(chǔ)概念(遞歸&迭代)

    詳解Java中二叉樹的基礎(chǔ)概念(遞歸&迭代)

    二叉樹(Binary?tree)是樹形結(jié)構(gòu)的一個(gè)重要類型。本文將通過(guò)圖片和示例代碼詳細(xì)為大家講解一下Java中的二叉樹的基礎(chǔ)概念,需要的可以參考一下
    2022-03-03
  • 詳解mybatis-plus實(shí)體類中字段和數(shù)據(jù)庫(kù)中字段名不對(duì)應(yīng)解決辦法

    詳解mybatis-plus實(shí)體類中字段和數(shù)據(jù)庫(kù)中字段名不對(duì)應(yīng)解決辦法

    這篇文章主要介紹了詳解mybatis-plus實(shí)體類中字段和數(shù)據(jù)庫(kù)中字段名不對(duì)應(yīng)解決辦法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2021-03-03
  • MyBatis?的?XML?配置文件和緩存使用步驟

    MyBatis?的?XML?配置文件和緩存使用步驟

    MyBatis?包含一個(gè)非常強(qiáng)大的查詢緩存特性,它可以非常方便地配置和定制,這篇文章主要介紹了MyBatis的XML配置文件和緩存,需要的朋友可以參考下
    2022-01-01
  • Spring Cloud Feign 自定義配置(重試、攔截與錯(cuò)誤碼處理) 代碼實(shí)踐

    Spring Cloud Feign 自定義配置(重試、攔截與錯(cuò)誤碼處理) 代碼實(shí)踐

    這篇文章主要介紹了Spring Cloud Feign 自定義配置(重試、攔截與錯(cuò)誤碼處理) 實(shí)踐,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-08-08
  • java實(shí)現(xiàn)多線程之定時(shí)器任務(wù)

    java實(shí)現(xiàn)多線程之定時(shí)器任務(wù)

    本篇文章主要介紹了java實(shí)現(xiàn)多線程之定時(shí)器任務(wù),小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2017-02-02

最新評(píng)論