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

Java數(shù)據(jù)結(jié)構(gòu)之復(fù)雜度篇

 更新時間:2022年01月19日 16:51:04   作者:ViolentAsteroid  
算法復(fù)雜度分為時間復(fù)雜度和空間復(fù)雜度。其作用:?時間復(fù)雜度是度量算法執(zhí)行的時間長短;而空間復(fù)雜度是度量算法所需存儲空間的大小

一.算法效率

算法效率分析分為兩種:時間效率、空間效率。其中時間效率被稱為時間復(fù)雜度,空間效率被稱為空間復(fù)雜度。

時間復(fù)雜度主要衡量的是一個算法的運行速度,而空間復(fù)雜度主要衡量一個算法所需要的額 外空間

由于早期計算機儲存容量很少,所以通常是浪費時間來換取空間。而隨著計算機的高速發(fā)展,計算機的存儲容量已經(jīng)達到了很高水平,所以現(xiàn)在通常是浪費空間換取時間

二. 時間復(fù)雜度

1.時間復(fù)雜度的概念

在計算機科學(xué)中,算法的時間復(fù)雜度是一個函數(shù),它定量描述了該算法的運行時間。但是一個算法執(zhí)行所耗費的時間,從理論上說,是不能算出來的,只有你把你的程序放在機器上跑起來,才能知道。全部算法的上機測試顯然是不現(xiàn)實的。于是才有了時間復(fù)雜度的分析方式:算法中的基本操作的執(zhí)行次數(shù),是為算法的時間復(fù)雜度。

有些算法的時間復(fù)雜度存在最壞、最好和平均情況。一般來說,實際情況中,我們所求的時間復(fù)雜度指的是最壞情況

最壞情況:任意輸入規(guī)模的最大運行次數(shù)(上界) 平均情況:任意輸入規(guī)模的期望運行次數(shù) 最好情況:任意輸入規(guī)模的最小運行次數(shù)(下界) 

2.大O的漸進表示方法

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

接下來我們看看推導(dǎo)大O階的基本原則

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

2、在修改后的運行次數(shù)函數(shù)中,只保留最高階項。

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

3.實例分析與計算

//計算bubbleSort的時間復(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;
            }
        }
    }

該算法最壞情況下執(zhí)行了(N*(N-1))/2次,通過推導(dǎo)大O階方法可以得出其時間復(fù)雜度為O(N) 

// 計算binarySearch的時間復(fù)雜度
    int binarySearch(int[] array, int value) {
        int begin = 0;
        int end = array.length - 1;
        while (begin <= end) {
            int mid = begin + ((end-begin) / 2);
            if (array[mid] < value)
                begin = mid + 1;
            else if (array[mid] > value)
                end = mid - 1;
            else
                return mid;
        }
        return -1;
    }

該算法最壞情況下執(zhí)行O(logN)次,時間復(fù)雜度為 O(logN)。ps:logN在算法分析中表示是底數(shù)為2,對數(shù)為N。有些地方會寫成lgN。該算法為二分查找,可以通過畫圖來借助理解,得出表達式為:N/2^X=1,X就是執(zhí)行操作的次數(shù)

// 計算階乘遞歸factorial的時間復(fù)雜度?
    long factorial(int N) {
        return N < 2 ? N : factorial(N-1) * N;
    }

 基本操作遞歸了N次,時間復(fù)雜度為O(N)

// 計算斐波那契遞歸fibonacci的時間復(fù)雜度
    int fibonacci(int N) {
        return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
    }

基本操作遞歸了2^N次,時間復(fù)雜度為O(2^N)

三.空間復(fù)雜度

1.空間復(fù)雜度的概念

空間復(fù)雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度 ??臻g復(fù)雜度不是程序占用了多少bytes的空間,而是算的是變量的個數(shù)。空間復(fù)雜度計算規(guī)則基本跟時間復(fù)雜度類似,也使用大O漸進表示法

2.實例分析與計算

// 計算bubbleSort的空間復(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;
            }
        }
    }

 該算法使用了常數(shù)個額外空間,所以空間復(fù)雜度為 O(1)

// 計算fibonacci的空間復(fù)雜度
    int[] 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;
    }

 該算法動態(tài)開辟了N個空間,空間復(fù)雜度為 O(N)

// 計算階乘遞歸Factorial的時間復(fù)雜度
    long factorial(int N) {
        return N < 2 ? N : factorial(N-1)*N;
    }

 該算法遞歸調(diào)用了N次,開辟了N個棧幀,每個棧幀使用了常數(shù)個空間。空間復(fù)雜度為O(N)

 四.寫在最后

由于期末專業(yè)課較多,加上自己自控力不足,導(dǎo)致斷更了一段時間。寒假決定洗心革面,把斷更的博文都補起來。博主在寫博客過程中可能出現(xiàn)一些錯誤,望大家斧正,以及由任何問題可以在評論區(qū)或者私信與博主交流。希望大家寒假能有所收獲,一起卷起來!

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之復(fù)雜度篇的文章就介紹到這了,更多相關(guān)Java 復(fù)雜度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 使用Spring @DependsOn控制bean加載順序的實例

    使用Spring @DependsOn控制bean加載順序的實例

    這篇文章主要介紹了使用Spring @DependsOn控制bean加載順序的實例講解,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-07-07
  • 淺談Java中注解Annotation的定義、使用、解析

    淺談Java中注解Annotation的定義、使用、解析

    下面小編就為大家?guī)硪黄獪\談Java中注解Annotation的定義、使用、解析。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-04-04
  • IDEA簡單實現(xiàn)登錄注冊頁面

    IDEA簡單實現(xiàn)登錄注冊頁面

    這篇文章主要介紹了IDEA簡單實現(xiàn)登錄注冊頁面,本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-12-12
  • 詳解MyBatis直接執(zhí)行SQL查詢及數(shù)據(jù)批量插入

    詳解MyBatis直接執(zhí)行SQL查詢及數(shù)據(jù)批量插入

    這篇文章主要介紹了MyBatis直接執(zhí)行SQL查詢及數(shù)據(jù)批量插入的相關(guān)知識,需要的朋友一起學(xué)習(xí)吧
    2016-01-01
  • Spring Cloud Feign接口返回流的實現(xiàn)

    Spring Cloud Feign接口返回流的實現(xiàn)

    這篇文章主要介紹了Spring Cloud Feign接口返回流的實現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-10-10
  • Java微信公眾平臺開發(fā)(6) 微信開發(fā)中的token獲取

    Java微信公眾平臺開發(fā)(6) 微信開發(fā)中的token獲取

    這篇文章主要為大家詳細(xì)介紹了Java微信公眾平臺開發(fā)第六步,微信開發(fā)中的token獲取,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-04-04
  • JavaEE Filter敏感詞過濾的方法實例詳解

    JavaEE Filter敏感詞過濾的方法實例詳解

    我們無論是在聊天還是在留言時,都有一些信息不希望別人看到。那么如果過濾這些關(guān)鍵詞呢?下面小編給大家分享JavaEE Filter敏感詞過濾的方法實例詳解,感興趣的朋友一起學(xué)習(xí)吧
    2016-05-05
  • java split結(jié)果去除空字符串的方法實現(xiàn)

    java split結(jié)果去除空字符串的方法實現(xiàn)

    在Java開發(fā)中,我們經(jīng)常需要對字符串進行分割操作,本文主要介紹了java split結(jié)果去除空字符串的方法實現(xiàn),具有一定的參考價值,感興趣的可以了解一下
    2023-10-10
  • java實現(xiàn)投票程序設(shè)計

    java實現(xiàn)投票程序設(shè)計

    這篇文章主要介紹了java實現(xiàn)投票程序設(shè)計,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2015-12-12
  • 詳解Java中while和do-while循環(huán)、break的使用

    詳解Java中while和do-while循環(huán)、break的使用

    本文介紹了循環(huán)結(jié)構(gòu)語句while和do-while循環(huán)、break的使用,while循環(huán)語句通過流程圖和語法語句結(jié)合一個求1~10的整數(shù)和的例子來幫助大家理解while循環(huán)的用法,感興趣的朋友跟隨小編來看看吧
    2020-11-11

最新評論