一、算法的復(fù)雜度
衡量一個(gè)算法的好壞，一般是從時(shí)間和空間兩個(gè)維度來衡量的，即時(shí)間復(fù)雜度和空間復(fù)雜度。
時(shí)間復(fù)雜度主要衡量一個(gè)算法的運(yùn)行快慢，而空間復(fù)雜度主要衡量一個(gè)算法運(yùn)行所需要的額外空間。
算法的時(shí)間復(fù)雜度
算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。
算法的空間復(fù)雜度
空間復(fù)雜度主要通過函數(shù)在運(yùn)行時(shí)候顯式申請的額外空間來確定。
?時(shí)間復(fù)雜度和空間復(fù)雜度都是由大O的漸近表示法來表示
推導(dǎo)大O階方法：
1、用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
2、在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
3、如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階。
?二、常見復(fù)雜度對比
?三、常見的時(shí)間復(fù)雜度和空間復(fù)雜度的計(jì)算
一、時(shí)間復(fù)雜度計(jì)算舉例
// 計(jì)算Func2的時(shí)間復(fù)雜度？
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);
}?O(N*2+10)，F(xiàn)unc2的時(shí)間復(fù)雜度為O(N)
// 計(jì)算Func3的時(shí)間復(fù)雜度？
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),若M>>N 則時(shí)間復(fù)雜度為 O(M),反之則為O(N).
? ? ? ? ? ? ? 若M==N則時(shí)間復(fù)雜度為O(N)或O(M).
// 計(jì)算Func4的時(shí)間復(fù)雜度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}?O(1)
// 計(jì)算BubbleSort的時(shí)間復(fù)雜度？
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;
}
}O((N+1)*(N)/2)? ?時(shí)間復(fù)雜度為O(N^2)
// 計(jì)算BinarySearch的時(shí)間復(fù)雜度？
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;
}二分查找? O(logn);ps：logN在算法分析中表示是底數(shù)為2，對數(shù)為N。
// 計(jì)算階乘遞歸Fac的時(shí)間復(fù)雜度？
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}O(N)
// 計(jì)算斐波那契遞歸Fib的時(shí)間復(fù)雜度？
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}
?O(logN)
?二、空間復(fù)雜度計(jì)算舉例
// 計(jì)算BubbleSort的空間復(fù)雜度？
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ù)雜度O(1),開了常數(shù)個(gè)
// 計(jì)算Fibonacci的空間復(fù)雜度？
// 返回斐波那契數(shù)列的前n項(xiàng)
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;
}O(N)
// 計(jì)算階乘遞歸Fac的空間復(fù)雜度？
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}O(N)
四、復(fù)雜度的oj練習(xí)
一、消失的數(shù)字
. - 力扣（LeetCode）. - 備戰(zhàn)技術(shù)面試？力扣提供海量技術(shù)面試資源，幫助你高效提升編程技能,輕松拿下世界 IT 名企 Dream Offer。https://leetcode-cn.com/problems/missing-number-lcci
大家看這道題是不是感覺有些熟悉呢？？
有沒有想到之前的那個(gè)單身狗問題呢？
這個(gè)題也跟那個(gè)題類似，先定義一個(gè)int類數(shù)，然后先與n個(gè)數(shù)異或，再與數(shù)組中的數(shù)異或
最后這個(gè)數(shù)就是數(shù)組中缺少的值.
因?yàn)?^1=0
int missingNumber(int* nums, int numsSize){
int num=0;
for(int i=0;i<=numsSize;i++){
num^=i;
}
for(int i=0;i<numsSize;i++){
num^=nums[i];
}
return num;
}
int missingNumber(int* nums, int numsSize){
int num=0;
for(int i=0;i<=numsSize;i++){
num+=i;
}
for(int i=0;i<numsSize;i++){
num-=nums[i];
}
return num;
}
二、旋轉(zhuǎn)數(shù)組
. - 力扣（LeetCode）. - 備戰(zhàn)技術(shù)面試？力扣提供海量技術(shù)面試資源，幫助你高效提升編程技能,輕松拿下世界 IT 名企 Dream Offer。https://leetcode-cn.com/problems/rotate-array
?這個(gè)題有兩種思路：
思路一：先將n-k個(gè)逆置，再將后k個(gè)逆置，最后直接整體逆置。（妙?。。。。?/p>
void rotate(int* nums, int numsSize, int k) {
k%=numsSize;
int tmp[numsSize];
int n=numsSize;
memcpy(tmp,nums+n-k,sizeof(int)*k);
memcpy(tmp+k,nums,sizeof(int)*(n-k));
memcpy(nums,tmp,sizeof(int)*(n));
}?文章來源：http://www.zghlxwxcb.cn/news/detail-847886.html
void Reverse(int*a,int left,int right){
int tmp=a[left];
a[left]=a[right];
a[right]=tmp;
right--;
left++;
}
void rotate(int* nums, int numsSize, int k) {
k%=numsSize;
//[0,numssize-k-1]
Reverse(nums,0,numsSize-k-1);
//[numssize-k,numssize-1]
Reverse(nums,numsSize-k,numsSize-1);
Reverse(nums,0,numsSize-1);
}今天的內(nèi)容就到此位置了，謝謝各位大佬觀看?。。?
文章來源地址http://www.zghlxwxcb.cn/news/detail-847886.html
到了這里，關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)：算法的時(shí)間復(fù)雜度和空間復(fù)雜度的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
