目錄
一.什么是空間復雜度與時間復雜度
1.1算法效率
1.2時間復雜度的概念
1.3空間復雜度的概念
二.如何計算常見算法的時間復雜度
2.1大O的漸近表示法
?使用規(guī)則
三.如何計算常見算法的空間復雜度
3.1 大O漸近表示法
3.2 面試題——消失的數(shù)字
?3.3 面試題——旋轉(zhuǎn)數(shù)組
一.什么是空間復雜度與時間復雜度
1.1算法效率
分為兩種，一種是時間效率，又稱時間復雜度，主要衡量算法的運行速度。另一種是空間效率，稱空間復雜度,衡量算法所需要的額外空間。
1.2時間復雜度的概念
簡單來說，算法中的基本操作的執(zhí)行次數(shù)，就是算法的時間復雜度。
1.3空間復雜度的概念
空間復雜度是對一個算法運行過程中臨時占用儲存空間大小的量度。一般使用大O漸近表示法表示。
二.如何計算常見算法的時間復雜度
2.1大O的漸近表示法
//實例一.請計算一下Func1基本操作執(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);
}我們可以知道準確的次數(shù)應該是N*N（每一次循環(huán)中嵌套循環(huán)都會循環(huán)N次，共N次循環(huán)所以是N*N次）+2*N（只循環(huán)2*N次）+10
這時候就會有關系：
令F(N)=N*N+2*N+10
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010
?注意點：
- 隨著N的增大，這個表達式中N^2對結(jié)果的影響是最大的。
- 時間復雜度是一個估算，是去看表達式中影響最大的那一項。
- 大O的漸進表示法，估算時間復雜度：O（N*2）。
?使用規(guī)則
- 用常數(shù)1取代運行時間中的所有加法常數(shù)。
- 在修改后的運行次數(shù)函數(shù)中，只保留最高階項。
- 如果最高階項存在且不是1，則去除與這個項目相乘的常數(shù)。得到的結(jié)果就是大O階。
//實例二，計算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);
}
?結(jié)果是O(N)，準確是2*N+10，之所以忽略2是因為隨著N無限增大，2已經(jīng)無法過多影響N。
//實例三.計算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);
}O（M+N）畢竟2個未知數(shù) 但如果有條件說M遠大于N，那么結(jié)果就為O（M）
如果條件是M與N差不多，那么結(jié)果為O（N)或O（M）。
//實例四.計算Func4的時間復雜度
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}O(1)? 只要是確定的常數(shù)次，都是O(1)
//實例五.計算strchr的時間復雜度
const char* strchr(const char* str, char character)
{
while (*str != '\0')
{
if (*str == character)
return str;
++str;
}
return NULL;
}相當于在一個字符數(shù)組中查找字符 。假設字符串長度是N，在下面字符串中找到字符’s‘,'d','x'的運行次數(shù)都是不一樣的。
?
?我們會發(fā)現(xiàn)有多種情況：
- 最壞情況：任意輸入規(guī)模的最大運行次數(shù)（上界）
- 平均情況：任意輸入規(guī)模的期望運行次數(shù)
- 最好情況：任意輸入規(guī)模的最小運行次數(shù)（下界）
例如：在一個長度為N數(shù)組中搜索一個數(shù)據(jù)x
最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到
在實際中一般情況關注的是算法的最壞運行情況，所有數(shù)組中搜索數(shù)據(jù)時間復雜度為O（N）
//案例六.計算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;
}
}怎么說呢，有點抽象吧。畢竟這個不是像之前一樣純看代碼，這一次是需要靠自己的理解把抽象代碼具體化，就比如本質(zhì)是冒泡排序，那我們就假想冒泡每一次執(zhí)行的過程是怎么樣的。
如數(shù)組arr[5]={0,1,2,3,4},0要換到4處最壞情況是4次（1，2，3，4，0），1換到3處最壞情況是3次，以此類推最后一個數(shù)為4時反而不用換了次數(shù)是0。
如下圖所示。（為方便理解這里把N-1~0換成N~1）
可以看到在列出所以結(jié)果后發(fā)現(xiàn)這是一個等差數(shù)列，最終我們用求和方式求出準確次數(shù)。再進行估算后得出O(N^2)
//案例七.計算BinarySearch的時間復雜度
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n;
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;
}這是一個經(jīng)典的二分查找案例，如果不懂其內(nèi)核的友友們可以移步這篇文章：
二分查找詳解
這里我們可以把這個數(shù)組想象成一張紙，里面的N個數(shù)想象成長度為N的紙，然后進行不斷的折半，不斷折半，這樣折半X次后，要么找到了，要么找不到。最后我們再把它還原回去。
通過這樣，我們得出了一個表達式：
//案例八.計算階乘遞歸Factorial的時間復雜度
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N - 1) * N;
}?
? 每次遞歸運算都是常數(shù)次，又因為遞歸調(diào)用N次，所以就是O(N)了。
????????
//案例九.計算斐波那契遞歸Fib的時間復雜度
long long Fib(size_t N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}執(zhí)行次數(shù)像一個金字塔一樣，1變2，2變3，次數(shù)不斷乘2.?
可以看出最終的時間復雜度是一個等比數(shù)列求和公式
?時間復雜度：O（2^N)
三.如何計算常見算法的空間復雜度
3.1 大O漸近表示法
//案例一.計算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;
}
}?
我們可以發(fā)現(xiàn)一共有5個變量，相當于開辟了5個空間，這樣一來：O(1)，因為5是常數(shù)。
在循環(huán)中走了N次，重復利用的是一個空間，只不過是變量出去會銷毀，但空間不會。時間是累計的，空間不是累計。
//案例二.計算Fibonacc1的空間復雜度
long long* Fibonacc1(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;
}?
我們可以知道準確的空間復雜度有O（N+6) 但實際是O(N)
其中malloc表達的含義是連續(xù)開辟了n+1的long long類型的數(shù)組。
//案例三.計算階乘遞歸Factorial的空間復雜度
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N - 1) * N;
}?
?雖然最后會銷毀，但空間復雜度計算的是累計最多使用的空間大小。
??
//案例四.計算斐波那契遞歸Fib的空間復雜度
long long Fib(size_t N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}? ?我們已經(jīng)知道時間復雜度是O(2^N)
我們先來用棧幀圖來表示：
一開始main開辟空間里面調(diào)用了Func1，F(xiàn)unc1也會開辟空間存儲變量a，結(jié)束后這個空間就銷毀了。接著又有Func2的調(diào)用，之所以能夠復用Func1的空間是因為它們都是類似的，都是創(chuàng)造一個int整型的變量（與值無關）。這就是地址相同的原因。
備注：兩個函數(shù)的地址是不一樣的，函數(shù)地址跟棧幀是沒有關系的！
在開辟空間的時候并不會Fib(N-1)和Fib(N-2)同時調(diào)用開辟，而是優(yōu)先順著Fib(N-1)往下繼續(xù)開辟空間，直到往下調(diào)用到Fib(2)時開始回歸，這時候Fib(2)的空間雖然銷毀了，但是只是把空間權限交還給了系統(tǒng)，當遞歸來到Fib(3)又會調(diào)用Fib(2)和Fib(1)，而這時候Fib(2)并不會重新開辟出新的空間，而是前往之前已經(jīng)銷毀的空間，相當于系統(tǒng)又重新把該處空間的開放權限交給了Fib(2)，所有順著箭頭我們會發(fā)現(xiàn)左側(cè)都是已經(jīng)開辟好的空間，一共有N處，這里的N處相當于一次性深入最多開辟的空間數(shù)，當遞進完成需要銷毀該處空間，回歸調(diào)用遇到曾經(jīng)已經(jīng)開辟（銷毀）過的空間時又重新使用這個空間。
換一種說法就是：酒店開了10間房，遇到Fib(2)遞進結(jié)束開始往上回歸時，相當于退房了。但房間還是在的，F(xiàn)ib(2)結(jié)束后就要調(diào)用Fib(1).而Fib(1)住進的房間就是Fib(2)退出的房間。
本質(zhì)還是最多房間數(shù)代表一次遞進所達到的最深程度，后面的都是重復利用罷了。不斷的退房，開房，直到所有人都退房的時候也就代表著遞歸結(jié)束了。
時間是累積的，一去不復返，但空間是可以重復利用的。因此空間復雜度為O(N)
3.2 面試題——消失的數(shù)字
原題鏈接：力扣——消失的數(shù)字
排序+遍歷：下一個數(shù)不等于下一個數(shù)據(jù)+1，這個下一個數(shù)就是消失的數(shù)字），?不過光排序(qsort)就花了很長時間了。
?
?時間復雜度為O（N）
int missingNumber(int* nums, int numsSize)
{
int N = numsSize;
int i = 0;
int ret = N * (N + 1) / 2;
for (i = 0; i < N; i++)
{
ret -= nums[i];
}
return ret;
}?
異或特點：先把二進制表示出來，然后相同為0，相異為1。無論什么數(shù)，相同的數(shù)異或就沒了。
?重點是不需要順序。
int missingNumber(int* nums, int numsSize)
{
int i = 0;
int j = 0;
int x = 0;
int N = numsSize;
for (i = 0; i < N; i++)
{
x ^= nums[i];
}
for (j = 0; j <= N; j++)
{
x ^= j;
}
return x;
}?3.3 面試題——旋轉(zhuǎn)數(shù)組
原題鏈接：力扣——旋轉(zhuǎn)數(shù)組
把最后一個元素放在tmp中，前面數(shù)組元素全部往右移，再把tmp放到第一位，以此類推。
至于它的時間與空間復雜度是有說法的，右旋一次執(zhí)行N次，那右旋K次應該是K*N次才對。
可是這是旋轉(zhuǎn)數(shù)組，你右旋0次與右旋7次結(jié)果是一樣的，所以k也分情況，最好的是只右旋了0次，最壞是右旋N-1次(第N次就又進入了輪回），所以時間復雜度也被分為O（1）與O (N^2)，按照規(guī)則我們?nèi)∽顗那闆rO (N^2)。
故該方法不符合條件，pass~。附上代碼：
void rotate(int* nums, int sumsSize, int k) { int N = sumsSize; if (k >= N) { k %= N; } while (k--) { int tmp = nums[N - 1]; for (int end = N - 2; end >= 0; end--) { nums[end + 1] = nums[end]; } nums[0] = tmp; } }
?
void rotate(int* nums, int sumsSize, int k)
{
int N = sumsSize;
int* tmp = (int*)malloc(sizeof(int) * N);//開辟與原數(shù)組空間同樣大小的新數(shù)組
k %= N;
memcpy(tmp, nums + N - k, sizeof(int) * k);//把原數(shù)組中從下標第N-k開始拷貝k個
memcpy(tmp, nums, sizeof(int) * (N - k));//把原數(shù)組從下標為0開始拷貝N-k個
memcpy(nums, tmp, sizeof(int) * N);//把tmp數(shù)組中所有的k個元素都拷貝回nums中去
free(tmp);//釋放空間
tmp = NULL;//置空
}?
就是一次性挪好幾個，把后k個拷貝到新數(shù)組里，再把前N-k個2拷貝到新數(shù)組，最后再把新數(shù)組一起拷貝回去，以空間換時間，但還是老問題，如果數(shù)組太大，空間可能達不到要求。
?最妙的方法?。?！文章來源：http://www.zghlxwxcb.cn/news/detail-726436.html
void Reverse(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 sumsSize, int k)
{
int N = sumsSize;
k %= N;
Reverse(nums, 0, N - k - 1);
Reverse(nums, N-k, N - 1);
Reverse(nums, 0, N-1);
}四.結(jié)語
關于復雜度的講解就此結(jié)束，希望可以幫助到大家理解。另外由于學校的課程緊張，我會停更一段時間的C語言專欄，目前先把數(shù)據(jù)結(jié)構搞定~?文章來源地址http://www.zghlxwxcb.cn/news/detail-726436.html
到了這里，關于數(shù)據(jù)結(jié)構——時間復雜度與空間復雜度的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
