目錄
1.演算法效率
1.1演算法的的復雜度
2.時間復雜度
2.1對時間復雜度的理解
2.2大O的漸進表示法
2.3用實體練習
3 空間復雜度
3.1實體
4.常見的時間復雜度以及復雜度oj練習
1.演算法效率
如何衡量一個演算法的好壞，比如下面的斐波那切數列
long long Fib(N)
{
if(N<3)
return 1;
return Fib(N-1)+Fib(N-2);
}雖然只有短短的4行代碼，當時這真的是簡單的嗎？
1.1演算法的的復雜度
演算法在撰寫成程式后，運行的時候需要消耗時間和空間（記憶體）資源，因此衡量一個演算法的復雜度是從時間和空間兩個維度來衡量的，而空間復雜度主要衡量一個演算法運行時所需要的額外空間，隨著計算機行業的快速發展，計算機的容量已經達到了很高的程度，所以現在沒有那么需要關注空間復雜度，
2.時間復雜度
2.1對時間復雜度的理解
在計算機科學中，演算法的時間復雜度是一個函式，他定量的描述了一個函式運行需要花的時間（準確的時間是算不出來的），而一個演算法所花費的時間與他的執行次數有關，所以演算法中的執行次數就是演算法的復雜度
2.2大O的漸進表示法
大O符號（Big O notatiion）：是用于描述函式漸進行為的函式（表示空間復雜度和時間復雜度）
推導大O階的方法：
1.用常數1取代運行時間中的所有加法常數，
2.在修改后的運行函式中，只保留最高階，
3.如果最高階存在且不是1，則去除與個專案相乘的常數，得到的結果就是大O階，
2.3用實體練習
int BinarySearch(int* a,int n,int x)
{
assert(a);
int left=0;
int right=n-1;
while(left<right)
{
int mid=left+((right-left)>>1);
if(a[mid]<x)
left=mid+1;
else if(a[mid]>x)
right=mid;
else
return mid;
}
return -1;
}
這是一個二分查找函式，假設這個陣列是有序的，求此時的演算法的時間復雜度？
在實際情況中，一般都是關注的是最壞的情況，所以上面的題是考慮的最壞的情況
實體2
void FUN(int a,int b)
{
int count=0;
for(int k=0;k<b;++k)
{
count++;
}
for(int k=0;k<a;k++)
{
count++;
}
printf("%d\n",count);
}這段代碼中一共運行a+b次，因為a和b是未知的，而且題目中為說明a和b大小的關系（如果a>>b,所以此時的復雜度為O（N）,一般寫成N,）所以這時候的時間復雜度為O(2N),根據推導大O的方法，所以此時的時間復雜度為O(N);
例3
long long Fib(size_t N)
{
if(N<3)
return 1;
return Fib(N-1)+Fib(N-2);
}
3 空間復雜度
和時間復雜度一樣，空間復雜度也是一個數學運算式，是對一個演算法在運行程序中臨時占用空間大小的復雜度，同樣，空間復雜度也不計算程式占用多少位元組，也用大O漸進表示法，
注意：函式運行時所需要的堆疊空間（存盤引數，區域變數，一些寄存資訊等等）在編譯期間就已經確定，因此這一些都不算在內，所以空間復雜度只有函式在運行的時候顯示申請的額外的空間來確定，
3.1實體
long long* fib(size_t n)
{
if(n==0)
return 0;
long long* fib=(long long*)malloc((n+1)*sizeof(long long));
fib[0]=0;
fib[1]=1;
for(int i=2;i<=n;i++)
{
fib[i]=fib[i-1]+fib[i-2];
}
return fib;
}這個例子中，每遞回一次，程式開辟一次一個額外的空間，一共開辟了N+1個額外空間，所以該例子的空間復雜度為O（N），
long long fac(size_t n)
{
if(n==0)
return 0;
return fac(n-1)*n;這個例子呼叫了N次，開辟了N 個堆疊幀，每個堆疊幀使用了常數個空間，空間復雜度為O(N)，
4.常見的時間復雜度以及復雜度oj練習
例1：
思路一：根據0~n之間的和為一個等引數列，求出和，再減去陣列里面的元素和，陣列元素求和一共呼叫了n次，此時的時間復雜度為O(N)，
思路二：
根據異或的特點,創建一個陣列包含了o~n的數字，將該陣列先和0異或，得到的值再和陣列nums進行異或，作何得到的就是兩個陣列中只出現一次的數字，即陣列nums中沒有的數字，因為異或是有交換律的，所以不難理解為什么會兩個得到那個沒有出現過的數字，
例2：
思路一：暴力求解，旋轉k次 ；結果：編譯不通過
思路二：開辟額外的空間，用空間換時間
此時的時間復雜度為O（N）,空間復雜度為O(N)；能不能使用O（1）來解決這個問題
思路三：對前n-k進行逆置，對后面k個進行逆置，最后最整體進行逆置
此時時間段復雜度為O(N),,空間復雜度為O(1）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/310568.html
標籤：其他
上一篇：【原始碼講解】Redis中記憶體優化的資料結構是如何設計的
下一篇：??酷炫回應式網路科技公司模網頁設計??（IT網路主題-HTML+CSS+JavaScript/javaweb前端大作業）