數據結構與算法拾遺八(認識複雜度)

lsd&xql 2022-06-23 17:15:37 阅读数:783

算法

時間複雜度

執行時間固定的操作都是常數時間的操作。
執行時間不固定的操作,都不是常熟時間操作。

首先是需要確定算法流程的總操作數量與樣本數量之間的錶達式關系,
只看錶達式最高階項的部分
這裏以選擇排序為例
首先從0-N-1的比特置找到最小值
(
N個數看一遍,找最小值(依次比較)
將找到的最小值放0比特置(O(1))
)
再從 1-N-1的比特置找到最小值
(
N-1個數看一遍,找最小值(依次比較)
將找到的最小值放0比特置(O(1))
)
2-N-1
(
N-2個數看一遍,找最小值(依次比較)
將找到的最小值放0比特置(O(1))
)
如上看加比較的次數是個等差數列
n+n-1+n-2…
再加上n次交換次數
得到 an^2 + bn,只看最高階 ->複雜度為O(n^2)

選擇排序代碼如下:

public static void selectionSort(int[] arr) {

if (arr == null || arr.length < 2) {

return;
}
// 0 ~ N-1 找到最小值,在哪,放到0比特置上
// 1 ~ n-1 找到最小值,在哪,放到1 比特置上
// 2 ~ n-1 找到最小值,在哪,放到2 比特置上
for (int i = 0; i < arr.length - 1; i++) {

int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
 // i ~ N-1 上找最小值的下標 
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {

int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}

再來看冒泡排序:
首先是在N個數的範圍上兩兩交換,把最大的放在最右邊(交換的複雜度為O(1))
接著是在N-1個數的範圍上兩兩交換,把最大的放在第N-1個比特置
然後再依次推下去
最後得到的時間複雜度為O(n^2)
代碼實現如下:

public static void bubbleSort(int[] arr) {

if (arr == null || arr.length < 2) {

return;
}
// 0 ~ N-1
// 0 ~ N-2
// 0 ~ N-3
for (int e = arr.length - 1; e > 0; e--) {
 // 0 ~ e
for (int i = 0; i < e; i++) {

if (arr[i] > arr[i + 1]) {

swap(arr, i, i + 1);
}
}
}
}
// 交換arr的i和j比特置上的值
public static void swap(int[] arr, int i, int j) {

arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}

再來推插入排序(相較於冒泡排序來說,冒泡排序無論是否已經排好序了都是要走O(n^2)的時間複雜度
,而插入排序如果對於已經排好部分序的數組時間複雜度會大大降低):
應以最差的情况下來估算
先是 0-1範圍上的有序,如果是倒序的數組的話,那麼需要交換一次
再是0-2範圍上的有序,如果是倒序的數組的話,那麼需要交換二次
再是0-3範圍上的有序,如果是倒序的數組的話,那麼需要交換三次
再是0-n範圍上的有序,如果是倒序的數組的話,那麼需要交換n-1次
這是一個等差數列那麼時間複雜度為O(n^2)
代碼如下:

public static void insertionSort(int[] arr) {

if (arr == null || arr.length < 2) {

return;
}
// 不止1個數
for (int i = 1; i < arr.length; i++) {
 // 0 ~ i 做到有序
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {

swap(arr, j, j + 1);
}
}
}
// i和j是一個比特置的話,會出錯
public static void swap(int[] arr, int i, int j) {

arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}

注意:
1、算法的過程,和具體的語言是無關的
2、想分析一個算法流程的時間複雜度的前提,是對該流程非常熟悉
3、一定要確保在拆分算法流程時,拆分出來的所有行為都是常數時間的操作,這
意味著寫算法時,對自己的通過的每一個系統API,都非常熟悉,否則將會影響你對時間複雜度的估算。
時間複雜度的意義:
當我們要處理的樣本量很大很大時,我們會發現低階項是什麼不是最重要的;每一項的系數是什 麼,不是最重要的。真正重要的就是最高階項是什麼。
這就是時間複雜度的意義,它是衡量算法流程的複雜程度的一種指標,該指標只與數據量有關,與過程之外的優化無關。

額外空間複雜度

你要實現一個算法流程,在實現算法流程的過程中,你需要開辟一些空間來支持你的算法流程。作為輸入參數的空間,不算額外空間。作為輸出結果的空間,也不算額外空間。因為這些都是必要的、和現實目標有關的。所以都不算。但除此之外,你的流程如果還需要開辟空間才能讓你的流程繼續下去。這部分空間就是額外空間。如果你的流程只需要開辟有限幾個變量,額外空間複雜度就是O(1)。

算法流程的常數項

我們會發現,時間複雜度這個指標,是忽略低階項和所有常數系數的。難道同樣時間複雜度的流程,在實際運行時候就一樣的好嗎?當然不是。時間複雜度只是一個很重要的指標而已。如果兩個時間複雜度一樣的算法,你還要去在時間上拼優劣,就進入到拼常數時間的階段,簡稱拼常數項。
常數項比拼方式:
放弃理論分析,生成隨機數據直接測。為什麼不去理論分析?不是不能純分析,而是沒必要。因為不同常數時間的操作,雖然都是固定時間,但還是有快慢之分的。比如,比特運算的常數時間原小於算術運算的常數時間,這兩個運算的常數時間又遠小於數組尋址的時間。所以如果純理論分析,往往會需要非常多的分析過程。都已經到了具體細節的程度,莫不如交給實驗數據好了。

算法的最優解

一般情况下,認為解决一個問題的算法流程,在時間複雜度的指標上,一定要盡可能的低,先滿足了時間複雜度最低這個指標之後,使用最少的空間的算法流程,叫這個問題的最優解。一般說起最優解都是忽略掉常數項這個因素的,因為這個因素只决定了實現層次的優化和考慮,而和怎麼解决整個問題的思想無關。
常見時間複雜度:
排名從好到差: O(1) O(logN) O(N) O(N*logN) O(N^2) O(N^3) … O(N^K) O(2^N) O(3^N) … O(K^N) O(N!)

版权声明:本文为[lsd&xql]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/174/202206231632202046.html