資料結構初階：演算法復雜度-有解無憂

文章目錄

- - 演算法復雜度
  - - 復雜度概念
    - 時間復雜度
    - - 時間復雜度定義
      - 大O漸進表示法
      - 大O階的推導規則
        Example 1
        Example 2
        Example 3
        Example 4
        Example 5
        Example 6
    - 空間復雜度
    - - 空間復雜度定義
      - Example 1
        Example 2
        Example 3
        Example 4
    - 常見復雜度
    - 復雜度OJ題
    - - 消失的數字
      - 思路 1
        思路 2
        思路 3
        思路 4
      - 旋轉陣列
      - 思路 1
        思路 2
        思路 3

演算法復雜度

復雜度概念

程式的運行時需要耗費一定的時間資源和空間(記憶體)資源，因此衡量一個演算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度，

時間復雜度主要衡量一個演算法的運行快慢，而空間復雜度主要衡量一個演算法運行所需要的額外空間，在計算機發展的早期，計算機的存盤容量很小，所以對空間復雜度很是在乎，現如今計算機的存盤容量已經達到了很高的程度，已不需要再特別關注一個演算法的空間復雜度，

時間復雜度

時間復雜度定義

演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，從理論上說，演算法執行所耗費的具體時間是不能算出來的，而即使真實測算出程式的運行時間，也因如機器的性能等種種原因無法描述演算法的優劣，

而且機器測算過于繁瑣，所以才有了時間復雜度這個分析方式，時間復雜度不計算具體時間而是演算法中的基本操作的執行次數，找到某潭訓本陳述句與問題規模 N N N 之間的數學運算式，就是算出了該演算法的時間復雜度，

如下列代碼：計算代碼中++count陳述句的執行次數，

void Func(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--) {
		++count;
        printf("hehe\n");
	}
}

從數學角度看，演算法的時間復雜度其實就是一個關于N的數學函式，如本題就是 F ( N ) = N 2 + 2 N + 10 F(N)=N^2+2N+10 F(N)=N2+2N+10，

大O漸進表示法

當N=10時F(N)=130，當N=100時F(N)=10210，當N=1000時F(N)=1002010，

可以看出如此精確的函式式在實際應用中，并沒有多大作用，只需要大概次數即可，當代碼的執行次數大到一定程度時，等式后面小項的影響就變得很小，保留最大項也就基本確定了結果，為了更方便的計算和描述演算法的復雜度，故提出了大O漸進表示法，

大O階的推導規則

大O符號：用于描述函式漸進行為的數學符號，

執行次數與N無關且為常數次時，用常數1表示，
只保留運行次數函式中舍去系數的最高階項，
若演算法存在最好最壞情況，則關注最壞情況，

由此可得上述演算法時間復雜度的大O階為 O ( N 2 ) O(N^2) O(N2)，

Example 1

void Func1(int N, int M) {
	int count = 0;
	for (int k = 0; k < M; ++k) {
		++count;
	}
	for (int k = 0; k < N; ++k) {
		++count;
	}
	printf("%d\n", count);
}

本題的時間復雜度是 O ( N + M ) O(N+M) O(N+M)，若標明 N > > M N>>M N>>M 則復雜度是 O ( N ) O(N) O(N)，反之則是 O ( M ) O(M) O(M)，若標明二者相近則是 O ( N ) O(N) O(N)或 O ( M ) O(M) O(M)，若 M M M , N N N 都是已知常數，則復雜度是 O ( 1 ) O(1) O(1)，

一般通常用 N N N 表示未知數，但 M M M , K K K 等等也行，

Example 2

void Func2(int N) {
	int count = 0;
	for (int k = 0; k < 100; ++ k) {
		++count;
	}
	printf("%d\n", count);
}

本題的運行次數是常數次，不管該常數多大，時間復雜度都是 O ( 1 ) O(1) O(1) ，

Example 3

void BubbleSort(int* a, int n) {
	assert(a);
	for (size_t end = n; end > 0; --end) {
		int exchange = 0;
		for (size_t i = 1; i < end; ++i) {
			if (a[i - 1] > a[i]) {
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

有的演算法會有最好情況，最壞情況，對于復雜度的計算我們通常采用最壞的情況作悲觀預期，很少有演算法會看平均情況，

冒泡排序就是其中之一，我們對其最差的情況分析，相鄰兩數相比，第一趟交換 N ? 1 N-1 N?1 次，第二趟交換 N ? 2 N-2 N?2 次，……，第 i i i 趟交換 N ? i N-i N?i 次，故精確的演算法次數應為 F ( N ) = N ? 1 + N ? 2 + . . . + N ? i + . . . + 1 + 0 = N × ( N ? 1 ) / 2 F(N)=N-1+N-2+...+N-i+...+1+0=N×(N-1)/2 F(N)=N?1+N?2+...+N?i+...+1+0=N×(N?1)/2 ，故復雜度為 O ( N 2 ) O(N^2) O(N2) ，

在這里插入圖片描述

也可以看比較的次數，由于每趟最后一次只比較不交換，所以每趟比較的次數都比交換的次數多一次，但是并不影響其的復雜度，

Example 4

int BinarySearch(int* a, int n, int x) {
	assert(a);
	int begin = 0;
	int end = n - 1;
	while (begin < end) {
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid;
		else
			return mid;
	}
	return -1;
}

計算演算法的復雜度不可僅看回圈的層數，還要看演算法的思想，二分查找同樣具有最好情況和最壞情況，仍然要對其最壞情況（找不到）進行分析，

對于這樣的每次折半的情況，可以形象的用“折紙法”理解，一張紙對折一次去掉一半再對折再舍棄，假設一共折了 x x x 次，就找到了該數字，也就是 2 x = N 2^x=N 2x=N，所以次數 x = l o g 2 N x=log_2N x=log2?N ，

對數階 O ( l o g 2 N ) O(log_2N) O(log2?N)，也可以省略底數寫成 O ( l o g N ) O(logN) O(logN)，二分查找這個對數階是非常優秀的演算法， 20 = l o g 2 ( 1000000 ) 20=log_2(1000000) 20=log2?(1000000)，一百萬個數僅需查找20次，

Example 5

long Factorial(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}

遞回演算法的復雜度取決于兩個因素：遞回深度和每次遞回呼叫次數，

遞回深度即是一共遞回的層數，也就是創建堆疊幀的次數，每次遞回呼叫次數是遞回函式內呼叫自身的次數，

顯然本題的深度是 O ( N ) O(N) O(N)，呼叫次數是 1 1 1，故復雜度是 O ( N ) O(N) O(N) ，

Example 6

long Fibonacci(size_t N)
{
    if(N < 3)
        return 1;
    return Fib(N-1) + Fib(N-2);
}

斐波那契遞回的思想是類似于二叉樹的，但是后面缺少了一部分，如圖所示：

如果沒有缺失的話就是完整二叉樹，將缺少的部分設為 X X X，精確次數就是 F ( N ) = 2 0 + 2 1 + 2 2 + . . . + 2 N ? 1 ? X = 2 N ? 1 ? X F(N)=2^0+2^1+2^2+...+2^{N-1}-X=2^N-1-X F(N)=20+21+22+...+2N?1?X=2N?1?X，由于 X X X遠小于 2 N ? 1 2^N-1 2N?1，故演算法復雜度為 O ( N ) = 2 N O(N)=2^N O(N)=2N，

空間復雜度

空間復雜度定義

空間復雜度也是數學運算式，度量演算法運行時臨時額外占存空間的大小，同樣空間復雜度不是無意義的實際占用的位元組數，空間復雜度計算臨時開辟變數的個數，基本規則規則和時間復雜度類似，也采用大O漸進表示法，

Example 1

void BubbleSort(int* a, int n) {
	assert(a);
	for (size_t end = n; end > 0; --end) {
		int exchange = 0;
		for (size_t i = 1; i < end; ++i) {
			if (a[i - 1] > a[i]) {
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

冒泡排序演算法僅創建了常數個變數，所以空間復雜度是 O ( 1 ) O(1) O(1)，

雖然變數end,i每次回圈都創建一次，但其實從記憶體角度看，每次所占空間并不會發生變化，一般都開辟在同一塊空間，

Example 2

long long* Fibonacci(size_t n) {
    if (n == 0)
        return NULL;
    long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n; ++i) {
        fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
    }
    return fibArray;
}

包括回圈變數和該斐波那契陣列，開辟量級為 N N N個的變數，故空間復雜度為 O ( N ) O(N) O(N) ，

Example 3

long long Factorial(size_t N)
{
    if(N == 0)
        return 1;
    return Fac(N - 1) * N;
}

每次遞回創建一個堆疊幀，每個堆疊幀中都是常數個變數， N N N次遞回的空間復雜度為 O ( N ) O(N) O(N) ，

遞回的空間復雜度與遞回深度有關，

Example 4

long Fibonacci(size_t N)
{
    if(N < 3)
        return 1;
    return Fib(N-1) + Fib(N-2);
}

斐波那契每次遞回同樣創建常數個變數，從斐波那契堆疊幀創建圖中可以看出，遞回中會有重復的項，這些重復的堆疊幀創建又銷毀，空間不同于時間是可以重復利用的，所以這些重復的堆疊幀僅占用一次的空間，所以 F i b ( N ) Fib(N) Fib(N), F i b ( N ? 1 ) Fib(N-1) Fib(N?1),…, F i b ( 1 ) Fib(1) Fib(1)這些堆疊幀都分配一次的空間足矣，故時間復雜度為 O ( N ) O(N) O(N) ，

常見復雜度

常見的演算法復雜度如下表，復雜度由上到下依次遞增：

簡稱	大O表示	示例
常數階	O ( 1 ) O(1) O(1)	k k k
對數階	O ( l o g n ) O(logn) O(logn)	k l o g 2 n klog_2n klog2?n
線性階	O ( n ) O(n) O(n)	k n kn kn
對數階	O ( n l o g n ) O(nlogn) O(nlogn)	k l o g 2 n klog_2n klog2?n
平方階	O ( n 2 ) O(n^2) O(n2)	k n 2 kn^2 kn2
立方階	O ( n 3 ) O(n^3) O(n3)	k n 3 kn^3 kn3
指數階	O ( 2 n ) O(2^n) O(2n)	k 2 n k2^n k2n
階乘階	O ( n ! ) O(n!) O(n!)	k n ! kn! kn!

最低的是常數次 O ( 1 ) O(1) O(1)，其次是對數階 O ( l o g n ) O(logn) O(logn)，然后是線性階 O ( n ) O(n) O(n)，再高就是平方階 O ( n 2 ) O(n^2) O(n2)，最大是指數階 O ( 2 n ) O(2^n) O(2n) ，前三個算是優秀演算法，而平方階是算是復雜的演算法，指數階階乘階的演算法萬萬不可取，

復雜度OJ題

消失的數字

思路 1

先排序陣列，檢查排序結果相鄰元素的差值，若差值不為1二者之間的缺值就是消失的數字，

時間復雜度為 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)，空間復雜度 O ( 1 ) O(1) O(1)

int cmp_int(const void* e1, const void* e2) {
    return *(int*)e1 - *(int*)e2;
}
int missingNumber(int* nums, int numsSize) {
    int flag = 1;
    //qsort
    qsort(nums, numsSize, sizeof(nums[0]), cmp_int);
    //元素個數為1
    if (numsSize == 1) {
        return numsSize - nums[0];
    }
    for (int i = 0; i < numsSize - 1; i++) {
        if (nums[i +1] - nums[i] != 1) {
            flag = 0;
            return nums[i] + 1;
        }
    }
    //缺失的數字為最大值或0
    if (flag == 1) {
        if (nums[0] == 0) {
            return numsSize;
        }
        else {
            return 0;
        }
    }
    return 0;
}

思路 2

將陣列中的元素寫到另一個陣列的對應下標位置上，沒有值的位置下標即為消失的數字，

時間復雜度為 O ( n ) O(n) O(n)，空間復雜度 O ( n ) O(n) O(n)

int missingNumber(int* nums, int numsSize) {
    int tmp[200000] = { 0 };
    memset(tmp, -1, 200000 * sizeof(int));
    //移入元素
    for (int i = 0; i < numsSize; i++) {
        tmp[nums[i]] = nums[i];
    }
    //尋找位置
    for (int i = 0; i <= numsSize; i++) {
        if(tmp[i] == -1) {
            return i;
        }
    }
    return 0;
}

思路 3

將0到n的元素之和減去陣列元素之和，得到的結果即為消失的數字，

時間復雜度為 O ( n ) O(n) O(n)，空間復雜度 O ( 1 ) O(1) O(1)

int missingNumber(int* nums, int numsSize) {
    int sumOfNum = 0;
    int sumOfNums = 0;
    for (int i = 0; i <= numsSize; i++) {
        sumOfNum += i;
    }
    for (int i = 0; i < numsSize; i++) {
        sumOfNums += nums[i];
    }
    return sumOfNum - sumOfNums;
}

思路 4

將 x x x與 [ 0 , n ] [0,n] [0,n] 的數字遍歷異或，在與陣列元素遍歷異或，最后結果即為消失的數字，

時間復雜度為 O ( n ) O(n) O(n)，空間復雜度 O ( 1 ) O(1) O(1)

int missingNumber(int* nums, int numsSize) {
    int xor = 0;
    //和[0,n]異或
    for (int i = 0; i <= numsSize; i++) {
        xor ^= i;
    }
    //和陣列異或
    for (int i = 0; i < numsSize; i++) {
        xor ^= nums[i];
    }
    return xor;
}

旋轉陣列

思路 1

陣列尾刪一次在頭插原陣列的尾元素，回圈 k k k 次，

時間復雜度為 O ( k × n ) O(k×n) O(k×n)，空間復雜度 O ( 1 ) O(1) O(1)

void rotate(int* nums, int numsSize, int k) {
    while (k--) {
        int tmp = nums[numsSize - 1];
        int end = numsSize - 1;
        while (end > 0) {
            nums[end] = nums[end - 1] ;
            end--;
        }
        nums[end] = tmp;
    }
}

思路 2

開辟同等大小的陣列，后 n ? k n-k n?k 個元素先轉移過去，在轉移前 k k k 個元素，在回傳陣列，

時間復雜度為 O ( n ) O(n) O(n)，空間復雜度 O ( n ) O(n) O(n)

void rotate(int* nums, int numsSize, int k) {
    int tmp[200] = { 0 };
    //后k個
    for (int i = 0; i < k; i++) {
        tmp[i] = nums[numsSize - k + i];
    }
    //前k個
    for (int i = 0; i < numsSize - k; i++) {
        tmp[i + k] = nums[i];
    }
    //轉移
    for (int i = 0; i < numsSize; i++) {
        nums[i] = tmp[i];
    }
}

思路 3

前 n ? k n-k n?k 個元素逆置，后 k k k 個元素逆置，再整體逆置，

時間復雜度為 O ( n ) O(n) O(n)，空間復雜度 O ( 1 ) O(1) O(1)

void reserve(int* nums, int left, int right) {
    while (left < right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k) {
    //1. 前n-k個逆置
    reserve(nums, 0, numsSize -k - 1);
    //2. 后k個逆置
    reserve(nums,numsSize - k, numsSize - 1);
    //3. 再整體逆置
    reserve(nums, 0, numsSize - 1);
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/321236.html

標籤：其他

上一篇：【資料結構】線性表與順序表，含順序表的各個插口代碼（筆記在gitee自取）

下一篇：13 Linux下的基礎IO