什么是時間復雜度和空間復雜度
??博客主頁：?自信不孤單
??文章專欄：數(shù)據(jù)結(jié)構(gòu)與算法
??代碼倉庫：破浪曉夢
??歡迎關注：歡迎大家點贊收藏+關注
1. 什么是數(shù)據(jù)結(jié)構(gòu)？
數(shù)據(jù)結(jié)構(gòu)(Data Structure)是計算機存儲、組織數(shù)據(jù)的方式，指相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。
2. 什么是算法？
算法(Algorithm):就是定義良好的計算過程，他取一個或一組的值為輸入，并產(chǎn)生出一個或一組值作為輸出。簡單來說算法就是一系列的計算步驟，用來將輸入數(shù)據(jù)轉(zhuǎn)化成輸出結(jié)果。
3. 算法的復雜度
算法在編寫成可執(zhí)行程序后，運行時需要耗費時間資源和空間(內(nèi)存)資源 。因衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。
時間復雜度主要衡量一個算法的運行快慢，而空間復雜度主要衡量一個算法運行所需要的額外空間。在計算機發(fā)展的早期，計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經(jīng)過計算機行業(yè)的迅速發(fā)展，計算機的存儲容量已經(jīng)達到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關注一個算法的空間復雜度。
3.1 時間復雜度
概念
時間復雜度的定義：在計算機科學中，算法的時間復雜度是一個函數(shù)，它定量描述了該算法的運行時間。
一個算法執(zhí)行所耗費的 時間理論上來說是算不出來的，因為它不僅僅與你寫的算法有關，還與運行這個算法的機器也有關系，如果你的機器很好，那么你所耗費的時間就可能會更少，所以，一個算法耗費的時間是需要放在機器上實際測驗才能知道的，但是我們總不能每個算法都拿來上機測試，來記錄該算法的時間，所以我們就有了時間復雜度這樣的分析方式。
一個算法所花費的時間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復雜度。
大O的線性表示法
大O符號（Big O notation）：是用于描述函數(shù)漸進行為的數(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);
}
請計算一下 Func1 中 ++count 語句總共執(zhí)行了多少次？
F ( N ) = N 2 + 2 ? N + 10 F(N)=N^2+2*N+10 F(N)=N2+2?N+10
- N = 10 F(N) = 130
- N = 100 F(N) = 10210
- N = 1000 F(N) = 1002010
實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進表示法。
大O的漸進表示法
大O符號（Big O notation）：是用于描述函數(shù)漸進行為的數(shù)學符號。
推導大O階方法：
1、用常數(shù)1取代運行時間中的所有加法常數(shù)。
2、在修改后的運行次數(shù)函數(shù)中，只保留最高階項。
3、如果最高階項存在且不是1，則去除與這個項目相乘的常數(shù)。得到的結(jié)果就是大O階。使用大O的漸進表示法以后，F(xiàn)unc1 的時間復雜度為：
O ( N 2 ) O(N^2) O(N2)
- N = 10 F(N) = 100
- N = 100 F(N) = 10000
- N = 1000 F(N) = 1000000
通過上面我們會發(fā)現(xiàn)大O的漸進表示法去掉了那些對結(jié)果影響不大的項，簡潔明了的表示出了執(zhí)行次數(shù)。
另外有些算法的時間復雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規(guī)模的最大運行次數(shù)(上界)
平均情況：任意輸入規(guī)模的期望運行次數(shù)
最好情況：任意輸入規(guī)模的最小運行次數(shù)(下界)例如：在一個長度為N數(shù)組中搜索一個數(shù)據(jù)x
最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到在實際中一般情況關注的是算法的最壞運行情況，所以數(shù)組中搜索數(shù)據(jù)時間復雜度為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); }實例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); }實例3：
// 計算Func4的時間復雜度？ void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++k) { ++count; } printf("%d\n", count); }實例4：
// 計算strchr的時間復雜度？ const char* strchr(const char* str, int character);實例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; } }實例6：
// 計算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; }實例7：
// 計算階乘遞歸Fac的時間復雜度？ long long Fac(size_t N) { if (0 == N) return 1; return Fac(N - 1) * N; }實例8：
// 計算斐波那契遞歸Fib的時間復雜度？ long long Fib(size_t N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); }
實例答案及分析：
實例1基本操作執(zhí)行了2N+10次，通過推導大O階方法知道，時間復雜度為 O(N)。
實例2基本操作執(zhí)行了M+N次，有兩個未知數(shù)M和N，時間復雜度為 O(N+M)。
實例3基本操作執(zhí)行了10次，通過推導大O階方法，時間復雜度為 O(1)。
實例4基本操作執(zhí)行最好1次，最壞N次，時間復雜度一般看最壞，時間復雜度為 O(N)。
實例5基本操作執(zhí)行最好N次，最壞執(zhí)行了(N*(N+1)/2次，通過推導大O階方法+時間復雜度一般看最
壞，時間復雜度為 O(N2)。實例6基本操作執(zhí)行最好1次，最壞O(logN)次，時間復雜度為 O(logN) ps：logN在算法分析中表示是底
數(shù)為2，對數(shù)為N。有些地方會寫成lgN。實例7通過計算分析發(fā)現(xiàn)基本操作遞歸了N次，時間復雜度為O(N)。
實例8通過計算分析發(fā)現(xiàn)基本操作遞歸了2N次，時間復雜度為O(2N)。(如圖)
3.2 空間復雜度
概念
空間復雜度也是一個數(shù)學表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度 。
空間復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數(shù)。
空間復雜度計算規(guī)則基本跟實踐復雜度類似，也使用大O漸進表示法。注意：函數(shù)運行時所需要的?？臻g(存儲參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復雜度主要通過函數(shù)在運行時候顯式申請的額外空間來確定。
常見空間復雜度計算舉例
實例1：
// 計算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; } }實例2：
// 計算Fibonacci的空間復雜度？ // 返回斐波那契數(shù)列的前n項 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; }實例3：
// 計算階乘遞歸Fac的空間復雜度？ long long Fac(size_t N) { if (N == 0) return 1; return Fac(N - 1) * N; }
實例答案及分析：
實例1使用了常數(shù)個額外空間，所以空間復雜度為 O(1)
實例2動態(tài)開辟了N個空間，空間復雜度為 O(N)
實例3遞歸調(diào)用了N次，開辟了N個棧幀，每個棧幀使用了常數(shù)個空間?？臻g復雜度為O(N)
常見復雜度對比
一般算法常見的復雜度如下：
文章來源：http://www.zghlxwxcb.cn/news/detail-413868.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-413868.html
到了這里，關于什么是時間復雜度和空間復雜度的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
