一.算法效率

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

時(shí)間復(fù)雜度主要衡量的是一個(gè)算法的運(yùn)行速度，而空間復(fù)雜度主要衡量一個(gè)算法所需要的額 外空間

由于早期計(jì)算機(jī)儲(chǔ)存容量很少，所以通常是浪費(fèi)時(shí)間來?yè)Q取空間。而隨著計(jì)算機(jī)的高速發(fā)展，計(jì)算機(jī)的存儲(chǔ)容量已經(jīng)達(dá)到了很高水平，所以現(xiàn)在通常是浪費(fèi)空間換取時(shí)間

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

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

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

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

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

2.大O的漸進(jìn)表示方法

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

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

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

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

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

3.實(shí)例分析與計(jì)算

//計(jì)算bubbleSort的時(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;
            }
        }
    }

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

// 計(jì)算binarySearch的時(shí)間復(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)次，時(shí)間復(fù)雜度為 O(logN)。ps：logN在算法分析中表示是底數(shù)為2，對(duì)數(shù)為N。有些地方會(huì)寫成lgN。該算法為二分查找，可以通過畫圖來借助理解，得出表達(dá)式為：N/2^X=1，X就是執(zhí)行操作的次數(shù)

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

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

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

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

三.空間復(fù)雜度

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

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

2.實(shí)例分析與計(jì)算

// 計(jì)算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ù)個(gè)額外空間，所以空間復(fù)雜度為 O(1)

// 計(jì)算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;
    }

 該算法動(dòng)態(tài)開辟了N個(gè)空間，空間復(fù)雜度為 O(N)

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

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

 四.寫在最后

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

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

最新評(píng)論