您好,登錄后才能下訂單哦!
這篇文章主要介紹“C語言時間復(fù)雜度與空間復(fù)雜度實例分析”,在日常操作中,相信很多人在C語言時間復(fù)雜度與空間復(fù)雜度實例分析問題上存在疑惑,小編查閱了各式資料,整理出簡單好用的操作方法,希望對大家解答”C語言時間復(fù)雜度與空間復(fù)雜度實例分析”的疑惑有所幫助!接下來,請跟著小編一起來學(xué)習(xí)吧!
如何衡量一個算法的好壞?比如對于以下斐波那契數(shù)列:
long long Fib(int N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); }
斐波那契數(shù)列用遞歸實現(xiàn)方式非常簡潔,但簡潔一定好嗎?那該如何衡量其好與壞呢?在學(xué)完時間復(fù)雜度會為您揭曉。
算法效率分析分為兩種:第一種是時間效率,第二種是空間效率。時間效率被稱為時間復(fù)雜度,而空間效率被稱作空間復(fù)雜度。 時間復(fù)雜度主要衡量的是一個算法的運(yùn)行速度,而空間復(fù)雜度主要衡量一個算法所需要的額外空間,在計算機(jī)發(fā)展的早期,計算機(jī)的存儲容量很小。所以對空間復(fù)雜度很是在乎。但是經(jīng)過計算機(jī)行業(yè)的迅速發(fā)展,計算機(jī)的存儲容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個算法的空間復(fù)雜度
一個算法所花費(fèi)的時間與其中語句的執(zhí)行次數(shù)成正比例,算法中的基本操作的執(zhí)行次數(shù),為算法的時間復(fù)雜度。
空間復(fù)雜度是對一個算法在運(yùn)行過程中臨時占用存儲空間大小的量度 ??臻g復(fù)雜度不是程序占用了多少bytes的空間,因為這個也沒太大意義,所以空間復(fù)雜度算的是變量的個數(shù)??臻g復(fù)雜度計算規(guī)則基本跟實踐復(fù)雜度類似,也使用大O漸進(jìn)表示法。
先看一串代碼:
// 請計算一下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); }
算法中的基本操作的執(zhí)行次數(shù),為算法的時間復(fù)雜度。顯而易見,這里Func1 執(zhí)行的最準(zhǔn)確操作次數(shù) :F(N)=N*N+2*N+10
例如F(10)=130、F(100)=10210、F(1000)=1002010
按理來說此題的時間復(fù)雜度就是上述的公式,其實不然。時間復(fù)雜度是一個估算,是去看表達(dá)式中影響最大的那一項。此題隨著N的增大,這個表達(dá)式中N^2對結(jié)果的影響是最大的
實際中我們計算時間復(fù)雜度時,我們其實并不一定要計算精確的執(zhí)行次數(shù),而只需要大概執(zhí)行次
數(shù),那么這里我們使用大O的漸進(jìn)表示法。,因而上題的時間復(fù)雜度為O(N^2)
大O符號(Big O notation):是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號。
推導(dǎo)大O階方法:
用常數(shù)1取代運(yùn)行時間中的所有加法常數(shù)。
在修改后的運(yùn)行次數(shù)函數(shù)中,只保留最高階項。
如果最高階項存在且不是1,則去除與這個項目相乘的常數(shù)。得到的結(jié)果就是大O階。
通過上面我們會發(fā)現(xiàn)大O的漸進(jìn)表示法去掉了那些對結(jié)果影響不大的項,簡潔明了的表示出了執(zhí)行次數(shù)。另外有些算法的時間復(fù)雜度存在最好、平均和最壞情況:
最壞情況:任意輸入規(guī)模的最大運(yùn)行次數(shù)(上界)
平均情況:任意輸入規(guī)模的期望運(yùn)行次數(shù)
最好情況:任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界)
例如:在一個長度為N數(shù)組中搜索一個數(shù)據(jù)x
最好情況:1次找到
最壞情況:N次找到
平均情況:N/2次找到
在實際中一般情況關(guān)注的是算法的最壞運(yùn)行情況,所以數(shù)組中搜索數(shù)據(jù)時間復(fù)雜度為O(N)
注意:遞歸算法時間復(fù)雜度計算
每次函數(shù)調(diào)用是O(1),那么就看他的遞歸次數(shù)
每次函數(shù)調(diào)用不是O(1),那么就看他的遞歸調(diào)用中次數(shù)的累加
例題:
例一:
// 計算Func2的時間復(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)
解析:此題中最準(zhǔn)確的次數(shù)為2*N+10,而其中影響最大的是N,可能有人覺著是2*N,但隨著N的不斷增大,2對結(jié)果的影響不是很大,況且要符合上述第三條規(guī)則:如果最高階項存在且不是1,則去除與這個項目相乘的常數(shù)。得到的結(jié)果就是大O階。所以把2去除掉,因而時間復(fù)雜度為O(N)
例二:
// 計算Func3的時間復(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ù),所以N和M都要帶著,但是如果題目明確M遠(yuǎn)大于N,那么時間復(fù)雜度就是O(M),如果M和N差不多大,那么時間復(fù)雜度就是O(M)或O(N)
例三:
// 計算Func4的時間復(fù)雜度? void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++k) { ++count; } printf("%d\n", count); }
答案:O(1)
解析:這里最準(zhǔn)確的次數(shù)是100,但是要符合大O的漸進(jìn)表示法的規(guī)則,用常數(shù)1取代運(yùn)行時間中的所有加法常數(shù)。所以時間復(fù)雜度就是O(1)
例四:
// 計算strchr的時間復(fù)雜度? const char* strchr(const char* str, char character) { while (*str != '\0') { if (*str == character) return str; ++str; } return NULL; }
答案:O(N)
解析:此題就要分情況了,這里假設(shè)字符串為abcdefghijklmn,如果目標(biāo)字符找的是g,則需要執(zhí)行N/2次,如果找到是a,則需要執(zhí)行1次,如果找n,則N次,所以要分情況,這里就出現(xiàn)了有些算法的時間復(fù)雜度存在最好O(1)、平均O(N/2)和最壞O(N)情況,但是在實際中一般情況關(guān)注的是算法的最壞運(yùn)行情況,所以此題時間復(fù)雜度為O(N)
例五:
// 計算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; } }
答案:O(N^2)
解析:此段代碼考到的是冒泡排序。第一趟的冒泡排序走了N次,第二趟走了N-1次,第三趟N-2,……最后就是1,次規(guī)律正合等差數(shù)列,求和即為(N+1)*N/2,當(dāng)然這個是最準(zhǔn)確的,這里還要找對結(jié)果影響最大的那一項,即N^2,所以時間復(fù)雜度是O(N^2)
例六:
// 計算BinarySearch的時間復(fù)雜度? 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; }
答案:O(logN)
解析:此題很明顯考到的是二分查找。假設(shè)數(shù)組長度為N,且找了X次,則1*2*2*2*2*……*2=N,即為2^X=N,則X等于log以2為底N的對數(shù),而算法的復(fù)雜度計算,喜歡省略簡寫成logN,因為很多地方不好寫底數(shù),所以此題時間復(fù)雜度為O(logN)
例七:
// 計算階乘遞歸Factorial的時間復(fù)雜度? long long Factorial(size_t N) { return N < 2 ? N : Factorial(N-1)*N; }
答案:O(N)
解析:如果N為10
例八:
long long Fib(int N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); }
這串代碼是上文最開始呈現(xiàn)的代碼,代碼風(fēng)格十分簡單,短短幾行便可完成斐波那契數(shù)列的計算,可看似這么簡潔的代碼真的“好”嗎?先來計算一下時間復(fù)雜度:
答案:O(2^N)
解析:
有上圖可以得知,第一行執(zhí)行1次,第二行執(zhí)行2^1次,第三行執(zhí)行2^2次,以此類推,是個等比數(shù)列,累計算下來再根據(jù)大O階表示法的規(guī)則得知,此斐波那契數(shù)列的時間復(fù)雜度為O(2^N)。
但是,根據(jù)2^N這個時間復(fù)雜度是個非常大的數(shù)字,當(dāng)n=10時,在VS環(huán)境下很快容易得到答案,但是當(dāng)n稍微再大一點(diǎn)比如說是50,就要等上很長一段時間才能將結(jié)果算出來,由此可見,簡潔的代碼不一定是最優(yōu)的代碼。
常見時間復(fù)雜度:O(N^2)、O(N)、O(logN)、O(1)
復(fù)雜度對比:
空間復(fù)雜度也是一個數(shù)學(xué)表達(dá)式,是對一個算法在運(yùn)行過程中臨時占用存儲空間大小的量度 ??臻g復(fù)雜度不是程序占用了多少bytes的空間,因為這個也沒太大意義,所以空間復(fù)雜度算的是變量的個數(shù)。
空間復(fù)雜度計算規(guī)則基本跟實踐復(fù)雜度類似,也使用大O漸進(jìn)表示法。
注意:函數(shù)運(yùn)行時所需要的??臻g(存儲參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了,因此空間復(fù)雜度主要通過函數(shù)在運(yùn)行時候顯式申請的額外空間來確定。
例題
例一:
// 計算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; } }
答案:O(1)
解析:這里其實總共開辟了三個空間,分別為end、exchange、i,既然是常數(shù)個變量,那么空間復(fù)雜度就是O(1),空間復(fù)雜度算的是申請的額外空間,所以跟上面的int*a和int n沒有關(guān)系。可能有人覺著這是個for循環(huán),exchange應(yīng)該開辟n次,其實每次循環(huán)進(jìn)來,exchange都會重新開辟,結(jié)束一次循環(huán)exchange銷毀,以此類推,exchange始終是同一個空間。
而什么時候會出現(xiàn)O(n)呢?
1、malloc一個數(shù)組
int *a = (int*)malloc(sizeof(int)*numsSize); //O(N)
此情況的前提是numsSize必須是個未知的數(shù)字,如果是具體數(shù)字,那么空間復(fù)雜度依舊是O(1)
2、變長數(shù)組
int a[numsSize]; //numsSize未知,O(N)
例二:
// 計算Fibonacci的空間復(fù)雜度? // 返回斐波那契數(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; }
答案:O(N+1)
解析:這里看到了malloc開辟了n+1個大小為long long類型的數(shù)組,看到這就不需要再過多計較后續(xù)創(chuàng)建了幾個變量,因為空間復(fù)雜度是估算,所以直接就是O(N)
例三:
// 計算階乘遞歸Fac的空間復(fù)雜度? long long Fac(size_t N) { if (N == 0) return 1; return Fac(N - 1) * N; }
答案:O(1)
解析: 這里遞歸函數(shù)是要建立棧幀的,而建立棧幀的個數(shù)為N個,每個棧幀的變量都是常數(shù)個,N個即空間復(fù)雜度為O(N)
例四:
// 計算斐波那契遞歸Fib的空間復(fù)雜度? long long Fib(size_t N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); }
答案:O(N)
解析:時間一去不復(fù)返,是累積的,空間回收以后是可以重復(fù)利用的。當(dāng)遞歸到Fib(3)的時候,此時調(diào)用Fib(2)和Fib(1),調(diào)到Fib(2)就可以返回了,此時Fib(2)的棧幀就銷毀了,此時再調(diào)用的Fib(1)和Fib(2)用的就是同一塊空間,同理Fib(N-1)總共建立了N-1個棧幀,同理再調(diào)用Fib(N-2)和剛才Fib(N-1)使用的是同一塊空間,充分說明了時間一去不復(fù)返,是累積的,空間回收以后是可以重復(fù)利用的。
題一:(消失的數(shù)字)
此題就明確了一個要求:想辦法在O(n)的時間內(nèi)完成,本題將提供兩種有效且可行的方法,正文開始:
法一:相加 - 相加
思想:
此題是在一串連續(xù)的整數(shù)中缺了一個數(shù),那我們就把理應(yīng)有的整數(shù)個數(shù)依次相加再減去原數(shù)組中缺一個數(shù)字的所有元素和即為我們想要的數(shù)字。
代碼如下:
int missingNumber(int* nums, int numsSize){ int sum1=0; int sum2=0; for(int i=0;i<numsSize+1;i++) { sum1+=i; } for(int i=0;i<numsSize;i++) { sum2+=nums[i]; } return sum1-sum2; }
法二:異或
思想:
正如示例2,這里假設(shè)一共有10個數(shù)字,那么這里nums數(shù)組就是 [ 0 - 9 ],不過其中缺了一個數(shù)字,我們已經(jīng)深知異或的運(yùn)算規(guī)則(相同為0,相異為1)以及兩個重要結(jié)論:1、兩個相同的數(shù)字異或等于0。2、0與任何數(shù)字異或等于該任意數(shù)字。因此,我們完全可以先把原數(shù)組的所有元素異或起來,再把理論上0-n依次遞增的所有元素都異或起來,然后兩塊再次異或得到的就是缺少的數(shù)字。
畫圖展示:
代碼如下:
int missingNumber(int* nums, int numsSize){ int n=0; for(int i=0;i<numsSize;i++) { n^=nums[i]; } for(int i=0;i<numsSize+1;i++) { n^=i; } return n; }
注意:第二個for循環(huán)中循環(huán)的次數(shù)要建立在numsSize的基礎(chǔ)上再加1,因為是缺少了一個數(shù)字,所以理論上數(shù)組的長度是在原基礎(chǔ)上加1的。
題二:(旋轉(zhuǎn)數(shù)組)
此題的進(jìn)階思想中就明確了使用空間復(fù)雜度為O(1)的算法來解決此問題,正文開始
法一:右旋K次,一次移動一個
思想:
首先,定義一個變量tmp把數(shù)組的最后一個元素保存起來。其次,把前N-1個值往后挪。最后,把tmp的值放到第一個位置。如圖所示:
此法時間復(fù)雜度為:O(N*K),空間復(fù)雜度O(1),此法的空間復(fù)雜度滿足題意了,但有個風(fēng)險,就是當(dāng)K%N=N-1時時間復(fù)雜度過大,為O(N^2),所以再看看有無更好方法:
法二: 額外開數(shù)組
思想:
額外開辟一個新數(shù)組,把后K個元素放到新數(shù)組前面,再把原數(shù)組N-K個元素拷貝到新數(shù)組后面。但是此法的時間復(fù)雜度是O(N),空間復(fù)雜度也是O(N),不符合題意,再換:
法三:三趟逆置
思想:
第一趟對它的前N-K個元素逆置,第二趟對它的后K個元素逆置,最后整體逆置。如圖所示:
此法非常巧妙,時間復(fù)雜度O(N),空間復(fù)雜度O(N),符合題意
代碼如下:
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 numsSize, int k){ k%=numsSize; reverse(nums,0,numsSize-k-1); reverse(nums,numsSize-k,numsSize-1); reverse(nums,0,numsSize-1); }
注意:這里當(dāng)k=7時,相當(dāng)于全部逆置完了一遍,也就是又回到了原來的樣子,是有規(guī)律可循的,所以真正逆置的次數(shù)為k%=numsSize;
到此,關(guān)于“C語言時間復(fù)雜度與空間復(fù)雜度實例分析”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識,請繼續(xù)關(guān)注億速云網(wǎng)站,小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。