C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度及空間復(fù)雜度簡(jiǎn)要分析
一、時(shí)間復(fù)雜度和空間復(fù)雜度是什么?
1.1算法效率定義
算法效率分為兩種,一種是時(shí)間效率——時(shí)間復(fù)雜度,另一種是空間效率——空間復(fù)雜度
1.2時(shí)間復(fù)雜度概念
時(shí)間復(fù)雜度,簡(jiǎn)言之就是你寫(xiě)一個(gè)代碼,它解決一個(gè)問(wèn)題上需要走多少步驟,需要花費(fèi)多長(zhǎng)時(shí)間。打個(gè)簡(jiǎn)單的比方:現(xiàn)在給10個(gè)數(shù),要求找到7在哪里1,2,3,4,5,6,7,8,9,10。我們要求寫(xiě)一個(gè)代碼,同學(xué)狗蛋寫(xiě)了一個(gè)暴力查找,從第一個(gè)數(shù)依次往后遍歷,他的算法要找7次,同學(xué)狗剩寫(xiě)了一個(gè)二分法查找,只要找2次,這就是時(shí)間復(fù)雜度的比較
算法中的基本操作的執(zhí)行次數(shù),為算法的時(shí)間復(fù)雜度
1.3空間復(fù)雜度概念
空間復(fù)雜度,是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度。舉個(gè)栗子:我們現(xiàn)在要求寫(xiě)一個(gè)代碼,狗蛋啪啪啪敲了一大堆變量,程序運(yùn)行了,狗剩就用了很少的變量,程序也運(yùn)行了。但是他們兩個(gè)在代碼運(yùn)行中變量多少不同,占用的內(nèi)存多少是不一樣的??臻g復(fù)雜度,它計(jì)算的是變量的個(gè)數(shù)。
二、如何計(jì)算常見(jiàn)算法的時(shí)間復(fù)雜度和空間復(fù)雜度
我們?cè)谟?jì)算時(shí)間/空間復(fù)雜度時(shí)用的都是大O漸進(jìn)表示法(是一種估算法)
2.1時(shí)間復(fù)雜度計(jì)算
我們以一個(gè)簡(jiǎn)單的函數(shù)舉例
代碼如下:
void func1(int n) { int i = 0; int j = 0; int k = 0; int count = 0; for (i = 0;i < n;i++) { for (j = 0;j < n;j++) { count++; } } for (k = 0;k < 3 * n - 1;k++) { count++; } }
試問(wèn):該函數(shù)如果被調(diào)用,要運(yùn)行多少次?
我們清楚的看出i進(jìn)去有n次,共有n個(gè)i,第一個(gè)for結(jié)束要運(yùn)行n^ 2次,第二個(gè)for要執(zhí)行3n-1次,共執(zhí)行n^ 2+3n-1次
那么我們這里的時(shí)間復(fù)雜度是否就是n^2+3n-1呢?答案是否的
我們前面說(shuō)過(guò),時(shí)間復(fù)雜度和空間復(fù)雜度用的都是大O漸進(jìn)表示法,是一種估算法
我們?nèi)〉闹担侨?duì)表達(dá)式中影響最大的那個(gè)
我們以n^ 2+3 * n-1這個(gè)式子進(jìn)行舉例:設(shè)f(n)=n^2+3n-1
n=1,f(n)=1+3-1=3
n=10,f(n)=100+30-1=129
n=100,f(n)=10000+300-1=10299
n=1000,f(n)=1002999
…
很容易發(fā)現(xiàn),對(duì)f(n)影響最大的是n^ 2,設(shè)g(n)=n^2
n=1,g(n)=1
n=10,g(n)=100
n=100,g(n)=10000
n=1000,g(n)=1000000
…
當(dāng)n越大,g(n)就越接近f(n)
那么這里的時(shí)間復(fù)雜度大O漸進(jìn)表達(dá)法寫(xiě)法是這樣的:O(n^2)
2.2空間復(fù)雜度計(jì)算
在學(xué)習(xí)空間復(fù)雜度的求解之前,我們要知道,空間復(fù)雜度也是用大O漸進(jìn)表達(dá)法進(jìn)行求解,我們計(jì)算的不是所占空間大小,而是變量的個(gè)數(shù)。先來(lái)看一段代碼:
代碼如下(示例):
#include<stdio.h> 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; } }
在上面這個(gè)代碼中,我們創(chuàng)建了三個(gè)變量分別是size_t end
、int exchange
、size_t i
,盡管我們這個(gè)函數(shù)會(huì)經(jīng)歷很多的循環(huán),但這三個(gè)變量是反復(fù)使用的,也就是說(shuō)他們所占的空間是被反復(fù)使用的,空間的多少是沒(méi)有變的,這里區(qū)別時(shí)間復(fù)雜度——時(shí)間是累計(jì)的,空間是不累計(jì)的(對(duì)于時(shí)間復(fù)雜度,每次循環(huán)都會(huì)被計(jì)算;對(duì)于空間復(fù)雜度,空間是可以被反復(fù)使用的)。
我們上面說(shuō)過(guò),空間復(fù)雜度計(jì)算也是用的大O漸進(jìn)表示法,對(duì)于常數(shù),我們統(tǒng)一用O(1)表示(大O漸進(jìn)表示法詳情見(jiàn)時(shí)間和空間復(fù)雜度篇1)
ps1:assert通常用于診斷程序中潛在的BUG,通過(guò)使用assert(condition), 當(dāng)condition為false時(shí),程序提前結(jié)束運(yùn)行,利于程序BUG的定位。
ps2:size_t是一種類(lèi)型,把它看作long unsigned int
我們?cè)賮?lái)看一段代碼:
代碼如下(示例):
//計(jì)算bubblesort的空間復(fù)雜度 #include<stdio.h> long long Factorial(size_t n) { return N < 2 ? N : Factorial(n - 1)*n; }
這段代碼是一個(gè)很簡(jiǎn)單的遞歸實(shí)現(xiàn)階乘運(yùn)算,那么它的空間復(fù)雜度是多少呢?我們先假設(shè)傳過(guò)去的n=10。
10傳過(guò)來(lái)我們會(huì)進(jìn)行10次遞歸,每次遞歸是創(chuàng)建一個(gè)函數(shù)棧幀(也就是一個(gè)空間),共創(chuàng)建10次,每一次的空間復(fù)雜度都是O(1)。把10換成n,也就是進(jìn)行n次遞歸,每次遞歸會(huì)創(chuàng)建1個(gè)函數(shù)棧幀,空間復(fù)雜度是O(n)。
ps:可能會(huì)有小伙伴問(wèn),那函數(shù)棧幀遞歸往回走的時(shí)候不是銷(xiāo)毀了嗎?注意:這里的空間復(fù)雜度是計(jì)算的“最壞、最多的情況”,況且不管是什么函數(shù),在使用過(guò)后其棧幀都會(huì)銷(xiāo)毀,空間復(fù)雜度算的是它用的空間最多的時(shí)候。
2.3快速推倒大O漸進(jìn)表達(dá)法
1.常數(shù)1代替所有加法運(yùn)算中的常數(shù)
2.只保留最高階(高數(shù)極限思想)
3.若最高階存在且不為常數(shù),則去除最高階的系數(shù),比如3*n^ 9,去掉系數(shù)變?yōu)閚^9
我們?cè)賮?lái)看兩個(gè)代碼訓(xùn)練一下
代碼1如下:
void func2(int n) { int i = 0; int k = 0; int count = 0; for (i = 0;i < 3n;i++) { count++; } for (k = 0;k < 6;k++) { count++; } }
這里f(n)=3n+6,它的大O漸進(jìn)表達(dá)法就是O(n)
代碼2如下:
void func3(int n) { int i = 0; int count = 0; for (i = 0;i < 1000;i++) { count++; } }
這里一眼就看出是運(yùn)行1000次,用什么來(lái)表示呢?前面說(shuō)過(guò):常數(shù)1代替所有加法運(yùn)算中的常數(shù),所以這里不管常數(shù)有多大,只要你只有一個(gè)常數(shù)都用O(1)表示
一些注意事項(xiàng):
O(1)這個(gè)時(shí)間復(fù)雜度的估值是不隨n的改變而改變的,以大白話說(shuō),不管你輸入的n是多少,我這個(gè)算法的效率是不變的
O(n)這個(gè)時(shí)間復(fù)雜度是隨n改變的
打個(gè)通俗的比方:設(shè)一個(gè)函數(shù)O(x)=1,那你x隨意多少,函數(shù)值都是1
設(shè)一個(gè)函數(shù)O(X)=x,那這里函數(shù)值就隨x變換而變換了
三、一些特殊的情況
有些算法的時(shí)間復(fù)雜度是存在最好、平均、最壞情況:
最壞情況:任意輸入規(guī)模的最大運(yùn)行次數(shù)(上界)
平均情況:任意輸入規(guī)模的期望運(yùn)行次數(shù)
最好情況:任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界)
不多說(shuō),舉例說(shuō)明:
代碼如下:
const char*strchr(char*str, char c) { while (*str != '\0') { if (*str == c) { return str; } ++str; } return NULL; }
上面的代碼是一個(gè)簡(jiǎn)單的查找字符的函數(shù),比如我們現(xiàn)在給一串字符共n個(gè)字符“aaaaba…aaac”(省略號(hào)省略a)
這里查找a一下子就找到了,查找b要點(diǎn)功夫,查找c就更慢了,如果查找d,不好意思,查無(wú)此d。
那么這里就出現(xiàn)了最好情況:一次找到O(1)
平均情況:O(n/2)
最差情況:O(n)
對(duì)于這里最壞情況可能有同學(xué)要說(shuō)為什么是O(n),你看最壞情況沒(méi)找到不是嗎?這里解釋是這樣的,你找c要n次,找d是找不到也要找n次才能確定找不到。
總結(jié)
本文介紹了時(shí)間和空間復(fù)雜度的定義及大O漸進(jìn)表達(dá)法的算法及一些特殊情況的解釋?zhuān)M麑?duì)屏幕前的讀者有所幫助,祝您學(xué)習(xí)愉快!
更多關(guān)于數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)及空間復(fù)雜度的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
c++函數(shù)中的指針參數(shù)與地址參數(shù)區(qū)別介紹
c++函數(shù)中的指針參數(shù)與地址參數(shù)區(qū)別介紹;可供參考2012-11-11C語(yǔ)言實(shí)現(xiàn)刮刮樂(lè)效果是示例代碼
這篇文章主要為大家詳細(xì)介紹了如何C語(yǔ)言模擬實(shí)現(xiàn)刮刮樂(lè)的效果,只要按下鼠標(biāo)左鍵并移動(dòng)就可以刮開(kāi)刮卡層,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-01-01一個(gè)string類(lèi)的簡(jiǎn)單實(shí)現(xiàn)案例
下面小編就為大家?guī)?lái)一篇一個(gè)string類(lèi)的簡(jiǎn)單實(shí)現(xiàn)案例。小編覺(jué)得挺不錯(cuò)的現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-01-01C++ 模擬實(shí)現(xiàn)list(迭代器)實(shí)現(xiàn)代碼
這篇文章主要介紹了C++ 模擬實(shí)現(xiàn)list(迭代器)實(shí)現(xiàn)代碼的相關(guān)資料,需要的朋友可以參考下2017-05-05淺談C++內(nèi)存分配及變長(zhǎng)數(shù)組的動(dòng)態(tài)分配
下面小編就為大家?guī)?lái)一篇淺談C++內(nèi)存分配及變長(zhǎng)數(shù)組的動(dòng)態(tài)分配。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-09-09C++ static詳解,類(lèi)中的static用法說(shuō)明
這篇文章主要介紹了C++ static詳解,類(lèi)中的static用法說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-07-07Qt編寫(xiě)地圖實(shí)現(xiàn)實(shí)時(shí)動(dòng)態(tài)軌跡效果
實(shí)時(shí)動(dòng)態(tài)軌跡主要是需要在地圖上動(dòng)態(tài)顯示GPS的運(yùn)動(dòng)軌跡,也是編寫(xiě)地圖時(shí)一個(gè)重要的功能。本文將利用Qt實(shí)現(xiàn)這一功能,需要的可以參考一下2022-02-02