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

Java算法之時(shí)間復(fù)雜度和空間復(fù)雜度的概念和計(jì)算

 更新時(shí)間:2021年05月06日 15:10:04   作者:愛敲代碼的三毛  
這篇文章主要介紹了Java算法之時(shí)間復(fù)雜度和空間復(fù)雜度的概念和計(jì)算,文中有非常詳細(xì)的代碼示例,對正在學(xué)習(xí)java的小伙伴們有非常好的幫助,需要的朋友可以參考下

一、算法效率

算法效率分析分為兩種:第一種是時(shí)間效率,第二種是空間效率。時(shí)間效率被稱為時(shí)間復(fù)雜度,而空間效率被稱作空間復(fù)雜度。 時(shí)間復(fù)雜度主要衡量的是一個(gè)算法的運(yùn)行速度,而空間復(fù)雜度主要衡量一個(gè)算法所需要的額外空間。

在計(jì)算機(jī)發(fā)展的早期,計(jì)算機(jī)的存儲容量很小。所以對空間復(fù)雜度很是在乎。但是經(jīng)過計(jì)算機(jī)行業(yè)的迅速發(fā)展,計(jì)算機(jī)的存儲容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個(gè)算法的空間復(fù)雜度。因?yàn)楝F(xiàn)在的內(nèi)存不像以前那么貴,所以經(jīng)常聽到過犧牲空間來換取時(shí)間的說法

二、時(shí)間復(fù)雜度

2.1 時(shí)間復(fù)雜度的概念

在計(jì)算機(jī)科學(xué)中,算法的時(shí)間復(fù)雜度是一個(gè)函數(shù),它定量描述了該算法的運(yùn)行時(shí)間。

算法中的基本操作的執(zhí)行次數(shù),為算法的時(shí)間復(fù)雜度。從理論上說,是不能算出來的,只有你把你的程序放在機(jī)器上跑起來,才能知道。但是我們需要每個(gè)算法都上機(jī)測試嗎?是可以都上機(jī)測試,但是這很麻煩,所以才有了時(shí)間復(fù)雜度這個(gè)分析方式。

一個(gè)算法所花費(fèi)的時(shí)間與其中語句的執(zhí)行次數(shù)成正比例,
算法中的基本操作的執(zhí)行次數(shù),為算法的時(shí)間復(fù)雜度。

2.2 大O的漸進(jìn)表示法

實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí),我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù),而只需要大概執(zhí)行次數(shù),那么這里我們使用大O的漸進(jìn)表示法

大O符號(Big O notation):是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號

(1)推導(dǎo)大O階方法

用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。在修改后的運(yùn)行次數(shù)函數(shù)中,只保留最高階項(xiàng)。如果最高階項(xiàng)存在且不是1,則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階

代碼如下(示例):

 void func(int N){
        int count = 0;//執(zhí)行1次
        for (int i = 0; i < N ; i++) {//執(zhí)行N*N次
            for (int j = 0; j < N ; j++) {
                count++;
            }
        }
        for (int k = 0; k < 2 * N ; k++) {//執(zhí)行2*N次
            count++;
        }
        int M = 10;//執(zhí)行1次
        while ((M--) > 0) {//執(zhí)行10次
            count++;
        }
        System.out.println(count);
    }

所以func方法的執(zhí)行次數(shù)為 1+N2+2*N+1+10

我看到func的執(zhí)行次數(shù),如果當(dāng)我們的N非常大時(shí),假設(shè)N = 100,那么這里的+1和+10是不是可以忽略了,因?yàn)?002=10000,在一萬面前+1和+10可以說是微乎其微了,所以+1和+10沒什么區(qū)別。

這就用到了前面說了推導(dǎo)大O階方法,

用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。

就變成了 1+N2+2*N+1+1

再來看

    在修改后的運(yùn)行次數(shù)函數(shù)中,只保留最高階項(xiàng)。

簡化后 N2

    如果最高階項(xiàng)存在且不是1,則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階

這里我們的最高階項(xiàng)是2,但前面沒有常數(shù)所以沒必要去除,如果N2前面還有個(gè)2就是2N2就要去除2變成 N2
所以使用大O的漸進(jìn)表示法以后,F(xiàn)unc的時(shí)間復(fù)雜度為 O(N2)

通過上面我們會(huì)發(fā)現(xiàn)大O的漸進(jìn)表示法去掉了那些對結(jié)果影響不大的項(xiàng),簡潔明了的表示出了執(zhí)行次數(shù)。時(shí)間復(fù)雜度是一個(gè)函數(shù),只能大致估一下這個(gè)算法的時(shí)間復(fù)雜度。

2.3 時(shí)間復(fù)雜度的三種情況

另外有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況。

(1) 最壞情況

最壞情況:任意輸入規(guī)模的最大運(yùn)行次數(shù)(上界) 也就是 O(N)

這里的N代表的是問題的規(guī)模

(2)最好情況

任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界) 也就是 O(1)

(3)平均情況

任意輸入規(guī)模的期望運(yùn)行次數(shù)

注意:這里的平均情況并不是最好和最壞情況相加的平均值,而是我們期望運(yùn)行的次數(shù),有時(shí)候平均情況可能和最好或者是最壞情況一樣。

在平常我們所說的時(shí)間復(fù)雜度一般說的都是算法的最壞情況

2.4 常見時(shí)間復(fù)雜度計(jì)算舉例

2.4.1 例子

示例1:

void func2(int N) {
	int count = 0;//1
	for (int k = 0; k < 2 * N ; k++) { //2*N
	   count++;
	}
	int M = 10;//1
	while ((M--) > 0) {//10
	   count++;
	}
	System.out.println(count);
}

1+2*N+1+10 通過推導(dǎo)大O階方法后:時(shí)間復(fù)雜度為 O(N)

示例2:

void func3(int N, int M) {
int count = 0;//常數(shù)可以不加
for (int k = 0; k < M; k++) {//M
   count++;
}
for (int k = 0; k < N ; k++) {//N
   count++;
}
System.out.println(count);
}

時(shí)間復(fù)雜度為:O(M+N)

示例3:

void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {//用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)
   count++;
}
System.out.println(count);
}

這里的時(shí)間復(fù)雜度為 O(1),因?yàn)閭鬟M(jìn)來的N并沒有使用

2.4.2 冒泡排序時(shí)間復(fù)雜度

示例4:

這是一個(gè)冒泡排序,我們來求一下它的最好最壞和平均情況的時(shí)間復(fù)雜度

void bubbleSort(int[] array) {
   for (int end = array.length; end > 0; end--) {
       boolean sorted = true;
       for (int i = 1; i < end; i++) {
       	if(array[i - 1] > array[i]){
       		Swap(array, i - 1, i);
               sorted = false;
           }
       }
       if (sorted == true) {
           break;
       }
   }
}

最好:O(N)
最壞:O(N2)
平均:O(N)

這是一個(gè)經(jīng)過優(yōu)化后的冒泡排序,最好的情況就是該組數(shù)據(jù)已經(jīng)是有序的了,所以只需走一遍就好了,也是是O(N).
而最壞的情況就把數(shù)組全部遍歷了一遍就是 N2
我們前面說過平均情況就是我么個(gè)期望的情況,我們期望的當(dāng)然就是O(N)

2.4.3 二分查找的時(shí)間復(fù)雜度

我們知道求時(shí)間復(fù)雜度一般求的都是最壞的情況,二分查找只有當(dāng)我們找最旁邊那兩個(gè)個(gè)數(shù)時(shí)才是最壞情況,我們就假設(shè)我們要找的就是最邊邊的那個(gè)數(shù)。

public static int binarySearch(int[] arr,int x){
            int left = 0;
            int right = arr.length-1;
            int mid = 0;//中間下標(biāo)

            while(left <= right){
                mid = left+(right-left)/2;
                if(arr[mid] > x){
                    right = mid - 1;
                }else if(arr[mid] < x){
                    left = mid+1;
                }else{
                    return mid;
                }
            }

            return -1;
  }

在這里插入圖片描述

所以二分查找的時(shí)間復(fù)雜度為 O(log2N)

2.4.4 遞歸的時(shí)間復(fù)雜度

遞歸的時(shí)間復(fù)雜度 = 遞歸的次數(shù)*每次遞歸執(zhí)行的操作的次數(shù)

示例1:

long factorial(int N) {
 return N < 2 ? N : factorial(N-1) * N;
}

這里的的遞歸次數(shù)為 N 次,這里沒有循環(huán),每次執(zhí)行的是一個(gè)三目操作符相當(dāng)于1次。所以為 N+1次,時(shí)間復(fù)雜度就是 O(N)。

示例2:

這是一個(gè)遞歸實(shí)現(xiàn)的斐波那契數(shù)列

public static int fib(int n){
        if(n==1||n==2){
            return 1;
        }else{
            return fib(n-1)+fib(n-2);
        }
}

斐波那契數(shù)列的遞歸次數(shù)其實(shí)就是一個(gè)等比數(shù)列求和,最后的執(zhí)行次數(shù)為 (2n) - 1,通過通過推導(dǎo)大O階方法最后的時(shí)間復(fù)雜度為 O(2N)

在這里插入圖片描述

時(shí)間復(fù)雜度只是一個(gè)大概的,當(dāng)數(shù)字足夠大時(shí)這里缺失的部分并不影響我們時(shí)間復(fù)雜度的計(jì)算。

三、空間復(fù)雜度

3.1 空間復(fù)雜度概念

空間復(fù)雜度是對一個(gè)算法在運(yùn)行過程中臨時(shí)(額外)占用存儲空間大小的量度
占用存儲空間大小的量度 。
空間復(fù)雜度不是程序占用了多少bytes的空間,因?yàn)檫@個(gè)也沒太大意義,所以空間復(fù)雜度算的是變量的個(gè)數(shù)。
空間復(fù)雜度計(jì)算規(guī)則基本跟實(shí)踐復(fù)雜度類似,也使用大O漸進(jìn)表示法

3.2 空間復(fù)雜度的計(jì)算

(1) 冒泡排序

這個(gè)冒泡排序的空間復(fù)雜度為 O(1)

為什么呢?因?yàn)榭臻g復(fù)雜度是為了解決一個(gè)問題額外申請了其他變量,這里的array數(shù)組并不是額外的它是必須的,但這里的 sorted 是額外申請的,它每循環(huán)一次就定一次為什么不是O(N)呢?因?yàn)槊垦h(huán)一次這個(gè)變量是不是不要了呢?所以來來回回就是這一個(gè)變量。

void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
     boolean sorted = true;//額外變量
     for (int i = 1; i < end; i++) {
         if (array[i - 1] > array[i]) {
             Swap(array, i - 1, i);
             sorted = false;
         }
     }
     if (sorted == true) {
         break;
     }
 }
}

(2) 斐波那契數(shù)列

這里的空間復(fù)雜度為 O(N)
這里為了求第1~N的斐波那契數(shù)列的代碼,為了解決這個(gè)問題申請了一個(gè)額外的數(shù)組的空間,空間大小為 N+1。因?yàn)?是常數(shù)項(xiàng),所以這個(gè)代碼的空間復(fù)雜度為 O(N)

public static long[] fibonacci(int n) {
        long[] fibArray = new long[n + 1];//額外空間
        fibArray[0] = 0;
        fibArray[1] = 1;
        for (int i = 2; i <= n ; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
        }
        return fibArray;
    }

(3)遞歸

這是一個(gè)求階層的遞歸,他的空間復(fù)雜度為 O(N)
因?yàn)檫f歸在遞的過程中,每遞一次都會(huì)都會(huì)創(chuàng)建一個(gè)臨時(shí)變量。

long factorial(int N) {
 return N < 2 ? N : factorial(N-1)*N;
}

四、總結(jié)

1.在平常我們所說的時(shí)間復(fù)雜度一般說的都是算法的最壞情況
2.時(shí)間復(fù)雜度度是一個(gè)函數(shù),這個(gè)函數(shù)只能大致估一下這個(gè)算法的時(shí)間復(fù)雜度
3.空間復(fù)雜度是個(gè)算法在運(yùn)行過程中額外占用存儲空間大小的量度

到此這篇關(guān)于Java算法之時(shí)間復(fù)雜度和空間復(fù)雜度的概念和計(jì)算的文章就介紹到這了,更多相關(guān)Java時(shí)間復(fù)雜度和空間復(fù)雜度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Spring Data Jpa 復(fù)合主鍵的實(shí)現(xiàn)

    Spring Data Jpa 復(fù)合主鍵的實(shí)現(xiàn)

    這篇文章主要介紹了Spring Data Jpa 復(fù)合主鍵的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-04-04
  • Java中的異常和處理機(jī)制實(shí)例詳解

    Java中的異常和處理機(jī)制實(shí)例詳解

    這篇文章主要介紹了Java中的異常和處理機(jī)制,結(jié)合實(shí)例形式詳細(xì)分析了Java異常與處理機(jī)制的相關(guān)概念、原理、用法及操作注意事項(xiàng),需要的朋友可以參考下
    2019-05-05
  • Java大數(shù)據(jù)處理的核心技術(shù)MapReduce框架

    Java大數(shù)據(jù)處理的核心技術(shù)MapReduce框架

    MapReduce是一種分布式計(jì)算框架,適用于大規(guī)模的數(shù)據(jù)處理。它將大數(shù)據(jù)分成多個(gè)小數(shù)據(jù)塊,通過Map和Reduce兩個(gè)階段對數(shù)據(jù)進(jìn)行處理和分析。MapReduce框架具有可靠、高效、可擴(kuò)展等特點(diǎn),已經(jīng)成為大數(shù)據(jù)處理的核心技術(shù)
    2023-05-05
  • Java終止循環(huán)體的具體實(shí)現(xiàn)

    Java終止循環(huán)體的具體實(shí)現(xiàn)

    這篇文章主要介紹了Java終止循環(huán)體的具體實(shí)現(xiàn),需要的朋友可以參考下
    2014-02-02
  • Springboot整合Mybatis傳值的常用方式總結(jié)

    Springboot整合Mybatis傳值的常用方式總結(jié)

    今天給大家?guī)淼氖顷P(guān)于Springboot的相關(guān)知識,文章圍繞著Springboot整合Mybatis傳值的常用方式展開,文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下
    2021-06-06
  • 詳解springboot設(shè)置默認(rèn)參數(shù)Springboot.setDefaultProperties(map)不生效解決

    詳解springboot設(shè)置默認(rèn)參數(shù)Springboot.setDefaultProperties(map)不生效解決

    這篇文章主要介紹了詳解springboot設(shè)置默認(rèn)參數(shù)Springboot.setDefaultProperties(map)不生效解決,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-07-07
  • Spring Boot集成Druid查看配置是否生效的方法

    Spring Boot集成Druid查看配置是否生效的方法

    本文主要介紹了Spring Boot集成Druid查看配置是否生效的方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-06-06
  • springmvc整合freemarker配置的詳細(xì)步驟

    springmvc整合freemarker配置的詳細(xì)步驟

    本篇文章主要介紹了springmvc整合freemarker的詳細(xì)步驟,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2017-05-05
  • 使用Mybatis生成樹形菜單的方法詳解

    使用Mybatis生成樹形菜單的方法詳解

    開發(fā)中我們難免會(huì)遇到各種樹形結(jié)構(gòu)展示的場景,比如用戶登錄系統(tǒng)后菜單的展示等,本文為大家整理了使用Mybatis生成樹形菜單的方法,感興趣的小伙伴可以了解一下
    2023-06-06
  • java?WebSocket?服務(wù)端實(shí)現(xiàn)代碼

    java?WebSocket?服務(wù)端實(shí)現(xiàn)代碼

    WebSocket協(xié)議是基于TCP的一種新的網(wǎng)絡(luò)協(xié)議。它實(shí)現(xiàn)了瀏覽器與服務(wù)器全雙工(full-duplex)通信——允許服務(wù)器主動(dòng)發(fā)送信息給客戶端,這篇文章主要介紹了java?WebSocket?服務(wù)端代碼,代碼簡單易懂,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2022-02-02

最新評論