1.算法效率

算法效率分析分為兩種：第一種是時(shí)間效率，第二種是空間效率。時(shí)間效率被稱為時(shí)間復(fù)雜度，而空間效率被稱作空間復(fù)雜度。

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

如今我們更關(guān)注的是時(shí)間復(fù)雜度，而對(duì)空間復(fù)雜度已不再關(guān)注。

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

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

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

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

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

請(qǐng)看如下代碼：

// 請(qǐng)計(jì)算一下func1基本操作執(zhí)行了多少次？
void func1(int N){
   int count = 0;
   for (int i = 0; i < N ; i++) {
       for (int j = 0; j < N ; j++) {//N^2次
           count++;
       }
   }
   for (int k = 0; k < 2 * N ; k++) {//2N次
       count++;
   }
   int M = 10;
   while ((M--) > 0){//10次
       count++;
   }
    System.out.println(count);
}

F(N) = N^2 + 2N + 10
Func1 執(zhí)行的基本操作次數(shù) ：
N = 10 , F(N) = 130
N = 100 , F(N) = 10210
N = 1000 , F(N) = 1002010

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

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

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

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

使用大O的漸進(jìn)表示法以后，F(xiàn)unc1的時(shí)間復(fù)雜度為 O(N^2)

另外有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù)(上限)
平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)
最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)

在實(shí)際中一般情況關(guān)注的是算法的最壞運(yùn)行情況，所以數(shù)組中搜索數(shù)據(jù)時(shí)間復(fù)雜度為O(N)

2.3常見(jiàn)時(shí)間復(fù)雜度計(jì)算

2.3.1常用的時(shí)間復(fù)雜度量級(jí)

2.3.2常見(jiàn)示例舉例

2.3.1.1計(jì)算 bubbleSort 的時(shí)間復(fù)雜度

// 計(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;
       }
   }
}

2.3.1.2計(jì)算 binarySearch 的時(shí)間復(fù)雜度

// 計(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; }

2.3.1.3計(jì)算階乘遞歸 factorial 的時(shí)間復(fù)雜度

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

2.3.1.4計(jì)算斐波那契遞歸 fibonacci 的時(shí)間復(fù)雜度

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

2.3.2示例答案及分析

2.3.2.1 bubbleSort 的時(shí)間復(fù)雜度

實(shí)例4基本操作執(zhí)行最好N次，最壞執(zhí)行了(N*(N-1))/2次，通過(guò)推導(dǎo)大O階方法+時(shí)間復(fù)雜度一般看最壞，時(shí)間復(fù)雜度為 O(N^2)

2.3.2.2 binarySearch 的時(shí)間復(fù)雜度

實(shí)例5基本操作執(zhí)行最好1次，最壞O(logN)次，時(shí)間復(fù)雜度為 O(logN) ps：logN在算法分析中表示是底數(shù)為2，對(duì)數(shù)為N。有些地方會(huì)寫(xiě)成lgN。（建議通過(guò)折半查找的方式講解logN是怎么計(jì)算出來(lái)的）(因?yàn)槎植檎颐看闻懦粢话氲牟贿m合值,一次二分剩下：n/2/2=4)

2.3.2.3 階乘遞歸 factorial 的時(shí)間復(fù)雜度

遞歸的時(shí)間復(fù)雜度=遞歸的次數(shù)*每次遞歸的次數(shù)

實(shí)例6通過(guò)計(jì)算分析發(fā)現(xiàn)基本操作遞歸了N次，時(shí)間復(fù)雜度為O(N)

2.3.2.4 斐波那契遞歸 fibonacci 的時(shí)間復(fù)雜度

實(shí)例7通過(guò)計(jì)算分析發(fā)現(xiàn)基本操作遞歸了2^N次 ,時(shí)間復(fù)雜度為 O(2^N)

3.空間復(fù)雜度

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

示例1：計(jì)算 bubbleSort 的空間復(fù)雜度？

// 計(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í)例1使用了常數(shù)個(gè)額外空間，所以空間復(fù)雜度為 O(1)
示例2：

// 計(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;
}

實(shí)例2動(dòng)態(tài)開(kāi)辟了N個(gè)空間，空間復(fù)雜度為 O(N)
示例3：

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

實(shí)例3遞歸調(diào)用了N次，開(kāi)辟了N個(gè)棧幀，每個(gè)棧幀使用常數(shù)的空間，空間復(fù)雜度為 O(N)

以上就是Java 關(guān)于時(shí)間復(fù)雜度和空間復(fù)雜度的深度刨析的詳細(xì)內(nèi)容，更多關(guān)于Java 時(shí)間復(fù)雜度和空間復(fù)雜度的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論