前言:
算法(Algorithm):就是定義良好的計算過程,他取一個或一組的值為輸入,并產生出一個或一組值作為 輸出。簡單來說算法就是一系列的計算步驟,用來將輸入數據轉化成輸出結果
一、算法效率
1.1 如何衡量一個算法的好壞
如何衡量一個算法的好壞呢?比如對于以下斐波那契數列:
long long Fib(int N)
{if(N < 3)return 1;return Fib(N-1) + Fib(N-2);
}
斐波那契數列的遞歸實現方式非常簡潔,但簡潔一定好嗎?那該如何衡量其好與壞呢?
1.2 算法的復雜度
算法在編寫成可執行程序后,運行時需要耗費時間資源和空間(內存)資源 。因此衡量一個算法的好壞,一般 是從時間和空間兩個維度來衡量的,即時間復雜度和空間復雜度。
時間復雜度主要衡量一個算法的運行快慢,而空間復雜度主要衡量一個算法運行所需要的額外空間。在計算機發展的早期,計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經過計算機行業的迅速發展,計算機的存儲容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個算法的空間復雜度。
復雜度在校招中的考察
常見復雜度對比
?
二、時間復雜度
2.1 時間復雜度的概念
時間復雜度的定義:在計算機科學中,算法的時間復雜度是一個函數,它定量描述了該算法的運行時間。一 個算法執行所耗費的時間,從理論上說,是不能算出來的,只有你把你的程序放在機器上跑起來,才能知道。但是我們需要每個算法都上機測試嗎?是可以都上機測試,但是這很麻煩,所以才有了時間復雜度這個 分析方式。一個算法所花費的時間與其中語句的執行次數成正比例,算法中的基本操作的執行次數,為算法的時間復雜度。
即:找到某條基本語句與問題規模N之間的數學表達式,就是算出了該算法的時間復雜度。
// 請計算一下Func1中++count語句總共執行了多少次?
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--){++count;}printf("%d\n", count);
}
實際中我們計算時間復雜度時,我們其實并不一定要計算精確的執行次數,而只需要大概執行次數,那么這里我們使用大O的漸進表示法。
2.2 大O的漸進表示法
大O符號(Big O notation):是用于描述函數漸進行為的數學符號。
推導大O階方法:
1、用常數1取代運行時間中的所有加法常數。
2、在修改后的運行次數函數中,只保留最高階項。
3、如果最高階項存在且不是1,則去除與這個項目相乘的常數。得到的結果就是大O階。
使用大O的漸進表示法以后,Func1的時間復雜度為:
O(N^2)
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項,簡潔明了的表示出了執行次數。
另外有些算法的時間復雜度存在最好、平均和最壞情況:
最壞情況:任意輸入規模的最大運行次數(上界)
平均情況:任意輸入規模的期望運行次數
最好情況:任意輸入規模的最小運行次數(下界)
例如:在一個長度為N數組中搜索一個數據x
最好情況:1次找到
最壞情況:N次找到
平均情況:N/2次找到
在實際中一般情況關注的是算法的最壞運行情況,所以數組中搜索數據時間復雜度為O(N)
三、常見時間復雜度計算舉例
實例1:
// 計算Func2的時間復雜度?
void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}
基本操作執行了2N+10次,通過推導大O階方法知道,時間復雜度為 O(N)
實例2:
// 計算Func3的時間復雜度?
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;}printf("%d\n", count);
}
基本操作執行了M+N次,有兩個未知數M和N,時間復雜度為 O(N+M)
實例3:
// 計算Func4的時間復雜度?
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}
基本操作執行了100次,通過推導大O階方法,時間復雜度為 O(1)
注:O(1)代表常數次
實例4:
// 計算strchr的時間復雜度?
const char * strchr ( const char * str, int character );
我們分析一下
while (*str)
{if (*str == charcter)return str;else++str;
}
基本操作執行最好1次,最壞N次,時間復雜度一般看最壞,時間復雜度為 O(N)
實例5:?
// 計算BubbleSort的時間復雜度?
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次,最壞執行了N*(N-1)/2次,通過推導大O階方法+時間復雜度一般看最壞,時間復雜度為 O(N^2)
實例6:
// 計算BinarySearch的時間復雜度?
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;// [begin, end]:begin和end是左閉右閉區間,因此有=號while (begin <= end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid - 1;elsereturn mid;}return -1;
}
分析二分查找的時間復雜度:?
查找區間的變化:
N
N/2?
N/4
N/8
……?1
二分查找什么情況下最壞?查找區間只剩一個數,或者找不到,也就是:N/2/2…/2 = 1
查找了多少次,就是除了多少個2,假設查找了x次 2^x = N
那么查找次數為:x=logN(底數忽略不寫)
則時間復雜度: O(logN)
因為寫的時候需要支持專業公式,否則不好寫底數,時間復雜度當中,為了方便,logN可以省略底數直接寫成logN,其他底層不能省略(其他底數也很少出現)
實例7:
// 計算階乘遞歸Fac的時間復雜度?
long long Fac(size_t N)
{if(0 == N)return 1;return Fac(N-1)*N;
}
遞歸時間復雜度:所有遞歸調用次數累加(等差數列)?
通過計算分析發現基本操作遞歸了N次,時間復雜度為O(N)。
實例8:
// 計算斐波那契遞歸Fib的時間復雜度?
long long Fib(size_t N)
{if(N < 3)return 1;return Fib(N-1) + Fib(N-2);
}
如下圖所示:每次遞歸都是以2倍的形式增長,累加求和,我們可以使用等比數列錯位相減法
??
計算分析發現基本操作遞歸了2^N次,時間復雜度為O(2^N)。
這種算法基本上是廢了,只有理論意義,實踐中太慢了。?
四、復雜度的OJ練習
1.消失的數字
OJ鏈接:消失的數字
?
思路一:先排序,再依次查找,如果下一個值不等于前一個+1,下一個值就是消失數字,如果我們使用冒泡排序進行排序,就不符合題目要求了,因為它的時間復雜度是O(N^2)
思路二:求和0到N,再依次減去數組中的值,剩下的那個值就是消失數字,累加的時間復雜度為O(N),如果N的數字比較大可能會導致棧溢出。
代碼如下:
思路三:我們可以使用異或,把數組中0到N的元素全部異或起來,相同為0相異為1,最后那個數字就是消失的數字,這樣還可以防止棧溢出
代碼如下:
int missingNumber(int* nums, int numsSize)
{int x = 0;int N = numsSize;for(int i = 0;i<numsSize;i++){x^=nums[i];}for(int j = 0;j<=numsSize;j++){x^=j;}return x;
}
2.輪轉數組
?OJ鏈接:輪轉數組
思路一:先寫出旋轉一次的函數,在調用k次,k的真實旋轉次數為k%=numsSize
代碼如下:
但是超出時間限制了
我們分析一下:
最壞情況 :k%N等于N-1 ->?O(N^2)
最好情況:k%N等于0
時間復雜度為O(N^2)
思路二:我們使用三段逆置,我們先讓前n-k個逆置一下,然后再把后k個逆置一下,最后整體逆置。
代碼如下:
void reverse(int*a,int left,int raght)
{while(left < raght){int temp = a[left];a[left] = a[raght];a[raght] = temp;++left;--raght;}
}
void rotate(int* nums, int numsSize, int k)
{k %= numsSize;reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);
}
時間復雜度為O(N),我們也可以使用memcpy
總結
時間復雜度是衡量算法執行效率的重要指標,它表示算法隨輸入數據規模增長時執行時間的變化趨勢。優化時間復雜度可以節省計算資源、提高系統性能、滿足實時性要求,并提升用戶體驗。在設計算法時,應充分考慮時間復雜度的優化,以實現高效、穩定的性能表現。?