快捷導(dǎo)航

Java數(shù)據(jù)結(jié)構(gòu)通關(guān)時間復(fù)雜度和空間復(fù)雜度

更新時間：2022年05月07日 14:30:33 作者：菜菜不恰菜

對于一個算法,其時間復(fù)雜度和空間復(fù)雜度往往是相互影響的,當(dāng)追求一個較好的時間復(fù)雜度時,可能會使空間復(fù)雜度的性能變差,即可能導(dǎo)致占用較多的存儲空間,這篇文章主要給大家介紹了關(guān)于Java時間復(fù)雜度、空間復(fù)雜度的相關(guān)資料,需要的朋友可以參考下

算法效率

算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。時間效率被稱為時間復(fù)雜度，而空間效率被稱作空間復(fù)雜度。時間復(fù)雜度主要衡量的是一個算法的運(yùn)行速度，而空間復(fù)雜度主要衡量一個算法所需要的額外空間,在計算機(jī)發(fā)展的早期,計算機(jī)的存儲容量很小。所以對空間復(fù)雜度很是在乎（以前是以時間換空間).但是經(jīng)過計算機(jī)行業(yè)的迅速發(fā)展，計算機(jī)的存儲容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個算法的空間復(fù) 雜度（現(xiàn)在是以空間換時間）。

時間復(fù)雜度

時間復(fù)雜度的定義：在計算機(jī)科學(xué)中，算法的時間復(fù)雜度是一個函數(shù)，它定量描述了該算法的運(yùn)行時間。一個算法執(zhí)行所耗費(fèi)的時間，從理論上說，是不能算出來的，只有你把你的程序放在機(jī)器上跑起來，才能知道。但是我們需要每個算法都上機(jī)測試嗎？是可以都上機(jī)測試，但是這很麻煩所以才有了時間復(fù)雜度這個分析方式。一個算法所花費(fèi)的時間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復(fù) 雜度。

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

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

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

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

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

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

來看些例子：

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

通過上面我們會發(fā)現(xiàn)大 O 的漸進(jìn)表示法去掉了那些對結(jié)果影響不大的項(xiàng) ，簡潔明了的表示出了執(zhí)行次數(shù)。

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

最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù) ( 上界 )

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

最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù) ( 下界 )

例如：在一個長度為 N 數(shù)組中搜索一個數(shù)據(jù) x

最好情況： 1 次找到

最壞情況： N 次找到

平均情況： N/2 次找到

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

例子二

// 計算func2的時間復(fù)雜度？
void func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; k++) {
   count++; }
int M = 10;
while ((M--) > 0) {
   count++; }
System.out.println(count);
}

例子三

// 計算func3的時間復(fù)雜度？
void func3(int N, int M) {
int count = 0;
for (int k = 0; k < M; k++) {
   count++; }
for (int k = 0; k < N ; k++) {
   count++; }
System.out.println(count);
}

例子四

// 計算func4的時間復(fù)雜度？
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
   count++; }
System.out.println(count);
}

例子五

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

例子六

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

例子七

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

空間復(fù)雜度

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

例子一

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

例子二

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

例子三

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

小結(jié)

這篇文章講的都是一些簡單的時間復(fù)雜度和空間復(fù)雜度的計算，如果有什么不正確的地方，歡迎大家指出來。

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

您可能感興趣的文章: