??個人主頁：fighting小澤
??作者簡介：目前正在學習C語言和數(shù)據(jù)結構
??博客專欄：數(shù)據(jù)結構
???歡迎關注：評論????點贊????留言????
1.算法效率
1.1 如何衡量一個算法的好壞
如何衡量一個算法的好壞呢？比如對于以下斐波那契數(shù)列：
long long Fib(int N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}
斐波那契數(shù)列的遞歸實現(xiàn)方式非常簡潔，但簡潔一定好嗎？那該如何衡量其好與壞呢？
1.2 算法的復雜度
算法在編寫成可執(zhí)行程序后，運行時需要耗費時間資源和空間(內(nèi)存)資源 。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。
時間復雜度主要衡量一個算法的運行快慢，而空間復雜度主要衡量一個算法運行所需要的額外空間。在計算機發(fā)展的早期，計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經(jīng)過計算機行業(yè)的迅速發(fā)展，計算機的存儲容量已經(jīng)達到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關注一個算法的空間復雜度。
注意：在不同的計算機上執(zhí)行相同的代碼也會因為計算機硬件的不同而花費不同的時間。
比如我們進行一個數(shù)量較多的冒泡排序，在 i3,1g內(nèi)存的機器和 i9,16g內(nèi)存的機器上花費的時間肯定不同
2.時間復雜度
2.1時間復雜度的概念
時間復雜度的定義：在計算機科學中，算法的時間復雜度是一個函數(shù)，它定量描述了該算法的運行時間。一個算法執(zhí)行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復雜度這個分析方式。一個算法所花費的時間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復雜度。
即：找到某條基本語句與問題規(guī)模N之間的數(shù)學表達式，就是算出了該算法的時間復雜度。
請計算一下Func1中++count語句總共執(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--)
{
++count;
}
printf("%d\n", count);
}
Fun進行了一次N * N 的循環(huán)，一次 2*N 的循環(huán)和一次 10 次的循環(huán)
即 Fun=(N * N) + (2 * N) + 10
- 當 N = 10 ， F(N) = 130
- 當 N = 100 ， F(N) = 10210
- 當 N = 1000 ，F(xiàn)(N) = 1002010
我們發(fā)現(xiàn)，隨著N的增大，后面項對結果的影響越小，所以實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進表示法。
2.2 大O的漸進表示法
大O符號（Big O notation）：是用于描述函數(shù)漸進行為的數(shù)學符號。
推導大O階方法：
1、用常數(shù)1取代運行時間中的所有加法常數(shù)。
2、在修改后的運行次數(shù)函數(shù)中，只保留最高階項。
3、如果最高階項存在且不是1，則去除與這個項目相乘的常數(shù)。得到的結果就是大O階。
使用大O的漸進表示法以后，F(xiàn)unc1的時間復雜度為：**O(N^2)
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
通過上面我們會發(fā)現(xiàn)大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執(zhí)行次數(shù)。
練習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);
}
Fun2一共執(zhí)行了2n+10次，所以它的時間復雜度是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);
}
Fun3一共執(zhí)行了M+N次，由于我們不知道M和N的關系，可能M特別大，可能N特別大，也可能它倆一樣大，M和N都會影響整個程序運行的時間，而M和N又是未知的，所以Fun3的時間復雜度是O(M+N)
練習3：
計算Func4的時間復雜度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}
Fun4執(zhí)行了100次，為常數(shù)次，所以它的時間復雜度為O(1)
練習4：
計算strchr的時間復雜度？
const char * strchr ( const char * str, int character );
strchr就是用來從一個字符串中找某個特定的字符，可能一開始就找到了，也可能很久都沒找到，但是我們在求時間復雜度的時候一般都是按照最壞打算來求的，也就是未知N次。它的時間復雜度為O(N)
補充
有些算法的時間復雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規(guī)模的最大運行次數(shù)(上界)
平均情況：任意輸入規(guī)模的期望運行次數(shù)
最好情況：任意輸入規(guī)模的最小運行次數(shù)(下界)
例如：在一個長度為N數(shù)組中搜索一個數(shù)據(jù)x
最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到
在實際中一般情況關注的是算法的最壞運行情況，所以數(shù)組中搜索數(shù)據(jù)時間復雜度為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;
}
}
在冒泡排序中會從第一個數(shù)開始不斷的進行兩個數(shù)的比較，然后不斷的把大數(shù)排在后面，所以每次比較的次數(shù)會減一，所以冒泡排序整體進行的次數(shù)為一個等差數(shù)列，用等差數(shù)列公式即 N * (1+N) / 2。它的最高項為N ^ 2，所以冒泡排序的時間復雜度為O(N ^ 2).
練習6：
計算strchr的時間復雜度？
const char * strchr ( const char * str, int character );
// 計算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;
}
}
// 計算BinarySearch的時間復雜度？
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
// [begin, end]：begin和end是左閉右閉區(qū)間，因此有=號
while (begin <= end)
{
int mid = begin + ((end-begin)>>1);
if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end = mid-1;
else
return mid;
}
return -1;
}
二分查找就是每次除以2嘛，2 ^ x = n,則 x = log n 。時間復雜度就為O(logN)。
注意：當我們想在一個有序數(shù)列找一個特別大的數(shù)時，暴力查找可能要進行幾百萬或者幾億次查找，而二分查找只用幾十次就可以了(有沒有感覺二分查找很厲害)
注：qsort的時間復雜度為（N*logN）,后面我們會講到的
練習7：
計算階乘遞歸Fac的時間復雜度？
long long Fac(int N)
{
if(0 == N)
return 1;
for(int i = 0;i < n; i++)
{
//....
}
return Fac(N-1)*N;
}
Fac一共進行N次遞歸，每次遞歸會進行N(當前的N)次循環(huán)，即進行1次，2次…N次循環(huán)，所以它的本質(zhì)也是一個等差數(shù)列，時間復雜度為O(N^2)
2.3 leetcode練習題
數(shù)組nums包含從0到n的所有整數(shù)，但其中缺了一個。請編寫代碼找出那個缺失的整數(shù)。你有辦法在O(n)時間內(nèi)完成嗎？力扣 ，消失的數(shù)字
方法1
我們可以把整個數(shù)組進行排序，然后遍歷。如果下一個數(shù)不是上一個數(shù)+1，則上一個數(shù)+1就是消失的數(shù)，這個方法大家可以自己嘗試一下，我們就不寫了
方法2（重點）
異或法：首先將sums所有的數(shù)進行異或(^)得到number1，number1再異或從0~n的數(shù)字得到number2，則得到的number2就是最終消失的那個數(shù)
int missingNumber(int* nums, int numsSize){
int i=0;
int x=0;
for(i=0;i<numsSize;i++)
{
x ^=nums[i];
}
for(i=0;i<numsSize+1;i++)
{
x ^= i;
}
return x;
}
方法3
等差數(shù)列求和法：我們可以通過等差數(shù)列求出0—n的值，然后減去數(shù)組的每一個元素，剩下的就是消失的數(shù)字
int missingNumber(int* nums, int numsSize)
{
int add_1 = 0;
int add_2 = 0;
add_1 = ( (0 + numsSize) * (numsSize + 1) ) / 2;
for(int i = 0; i < numsSize; i++)
{
add_2 += nums[i];
}
return add_1 - add_2;
}
結尾
這些就是我給大家分享的關于算法的復雜度的知識啦，希望我們都能有所收獲
先贊后看,養(yǎng)成習慣??！^ _ ^
碼字不易，大家的支持就是我堅持下去的動力，點贊后不要忘了關注我哦！文章來源：http://www.zghlxwxcb.cn/news/detail-420823.html
如有錯誤，還請您批評改正(?ì _ í?)文章來源地址http://www.zghlxwxcb.cn/news/detail-420823.html
到了這里，關于【數(shù)據(jù)結構】算法的時間復雜度和空間復雜度 (上)（附leetcode練習題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
