數(shù)據(jù)結(jié)構(gòu)之時(shí)間復(fù)雜度-空間復(fù)雜度

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)之時(shí)間復(fù)雜度-空間復(fù)雜度。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

大家好，我是深魚~

1.數(shù)據(jù)結(jié)構(gòu)前言

1.1什么是數(shù)據(jù)結(jié)構(gòu)

1.2什么是算法

1.3數(shù)據(jù)結(jié)構(gòu)和算法的重要性

1.4如何學(xué)好數(shù)據(jù)結(jié)構(gòu)和算法

2.算法的效率

3.時(shí)間復(fù)雜度

3.1時(shí)間復(fù)雜度的概念

3.2大O的漸進(jìn)表示法

【實(shí)例1】：雙重循環(huán)的時(shí)間復(fù)雜度：O（N)

【實(shí)例2】：雙重循環(huán)的時(shí)間復(fù)雜度：O（N+M）

【實(shí)例3】：常數(shù)循環(huán)的時(shí)間復(fù)雜度：O（1）

【實(shí)例4】：strchr的時(shí)間復(fù)雜度：O(N)

【實(shí)例5】：冒泡排序的時(shí)間復(fù)雜度：O（N^2)

【實(shí)例6】：二分查找的時(shí)間復(fù)雜度：O（log2N）

【實(shí)例7】：階乘遞歸的時(shí)間復(fù)雜度:O(N）

【實(shí)例8】：斐波那契遞歸的時(shí)間復(fù)雜度：O（2^N)

?4.空間復(fù)雜度

【實(shí)例1】：冒泡排序的空間復(fù)雜度：O（1）

【實(shí)例2】：斐波那契遞歸的空間復(fù)雜度：O（N）

【實(shí)例3】：函數(shù)階乘遞歸的空間復(fù)雜度：O(N)

?【拓展】遞歸版斐波那契數(shù)列的空間復(fù)雜度：O（N）

1.數(shù)據(jù)結(jié)構(gòu)前言

1.1什么是數(shù)據(jù)結(jié)構(gòu)

實(shí)現(xiàn)一些項(xiàng)目，需要在內(nèi)存中將數(shù)據(jù)存儲起來，數(shù)據(jù)結(jié)構(gòu)就是計(jì)算機(jī)存儲、組織數(shù)據(jù)的方式。指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。eg：數(shù)組，鏈表，樹...

1.2什么是算法

算法簡單來說就是一系列的計(jì)算步驟，用來將輸入數(shù)據(jù)轉(zhuǎn)化為輸出結(jié)果的。常見的算法有：排序，查找，查重，推薦算法...

1.3數(shù)據(jù)結(jié)構(gòu)和算法的重要性

在校招的筆試中會有很多有關(guān)數(shù)據(jù)結(jié)構(gòu)和算法的題

可以看看鏈接，在未來工作中：

數(shù)據(jù)結(jié)構(gòu)和算法對一個程序員來說的重要性

1.4如何學(xué)好數(shù)據(jù)結(jié)構(gòu)和算法

<1>多敲代碼

<2>注重畫圖和思考

2.算法的效率

算法的效率看兩點(diǎn)，第一點(diǎn)看時(shí)間效率，也就是時(shí)間復(fù)雜度，第二點(diǎn)看空間效率，也就是空間復(fù)雜度，但是隨著計(jì)算機(jī)行業(yè)的發(fā)展，計(jì)算機(jī)的存儲容量已經(jīng)達(dá)到了很高的程度，所以如今我們不用太關(guān)注一個算法的空間復(fù)雜度

3.時(shí)間復(fù)雜度

3.1時(shí)間復(fù)雜度的概念

算法的時(shí)間復(fù)雜度是數(shù)學(xué)里面一個帶有未知數(shù)的函數(shù)表達(dá)式，算法的復(fù)雜度不是看這個算法的運(yùn)行時(shí)間，因?yàn)?span style="color:#956fe7;">環(huán)境不同，具體的運(yùn)行時(shí)間就不一樣，eg：10年前2核cpu、2g內(nèi)存的機(jī)器和今天8核cpu、8g內(nèi)存的機(jī)器，運(yùn)行的時(shí)間就不一樣。算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度

3.2大O的漸進(jìn)表示法

請計(jì)算一下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);
}

Func1 執(zhí)行的基本操作次數(shù) ：F（N)=N*N+2*N+10

當(dāng)N = 10? ? ? ? F(N) = 130

當(dāng)N = 100? ? ? F(N) = 10210

當(dāng)N = 1000? ?F(N) = 1002010

N越大，后兩項(xiàng)對結(jié)果的影響越小，所以實(shí)際計(jì)算時(shí)間復(fù)雜度時(shí)，我們只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進(jìn)表示法(估算），即時(shí)間復(fù)雜度：O（N^2)

大O漸進(jìn)表示法：

(1)用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)

(2)在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)

(3)如果最高階存在且不是1，則取除與這個項(xiàng)目相乘的常數(shù)

【實(shí)例1】：雙重循環(huán)的時(shí)間復(fù)雜度：O（N)

本來應(yīng)該是2*N，根據(jù)大O漸進(jìn)表示法（3）簡化為O(N)

// 計(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);
}

【實(shí)例2】：雙重循環(huán)的時(shí)間復(fù)雜度：O（N+M）

（如果前提：M>>N,那么時(shí)間復(fù)雜度就是O（M）;

? ? ? ? ? ? ? ? ? ? ? N>>M,那么時(shí)間復(fù)雜度就是O（N）;

? ? ? ? ? ? ? ? ? ? ? M和N差不多,那么時(shí)間復(fù)雜度O（M）或O（N）都可以)

一般情況下時(shí)間復(fù)雜度計(jì)算時(shí)未知數(shù)都是用的N，但是也可以使用M，K等等其他的

// 計(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);
}

【實(shí)例3】：常數(shù)循環(huán)的時(shí)間復(fù)雜度：O（1）

本來是100，根據(jù)大O漸進(jìn)表示法（1）簡化為O(1)

（O（1）不是代表算法運(yùn)行一次，而是常數(shù)次）

// 計(jì)算Func4的時(shí)間復(fù)雜度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}

【實(shí)例4】：strchr的時(shí)間復(fù)雜度：O(N)

// 計(jì)算strchr的時(shí)間復(fù)雜度？
const char * strchr ( const char * str, int character );

strchr函數(shù)的邏輯實(shí)際就是下面這個

while（*str）

{

? ? ?if（*str==character)

? ? ? ? ? ? return str;

? ? ?else

? ? ? ? ? ?++str;

}

?以hello world這個字符串為例：

假設(shè)查找的是h：? ? ? 1 最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界)

假設(shè)查找的是w：? ? ?N/2 平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)(大概就是最好最壞相加/2）

假設(shè)查找的是d：? ? ? ?N 最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù)(上界)

當(dāng)一個算法隨著輸入的不同，時(shí)間復(fù)雜度不同，時(shí)間復(fù)雜度做悲觀預(yù)期，看最壞的情況（即這個例子的時(shí)間復(fù)雜度是O（N））

【實(shí)例5】：冒泡排序的時(shí)間復(fù)雜度：O（N^2)

// 計(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;
} 
}

時(shí)間復(fù)雜度：N-1,N-2,N-3...1? ?精確值也就是N*（N-1)/2,那么大O的漸變表示法就是O（N^2)

算時(shí)間復(fù)雜度不能只看幾層循環(huán)，而要去看他的思想

【實(shí)例6】：二分查找的時(shí)間復(fù)雜度：O（log2N）

// 計(jì)算BinarySearch的時(shí)間復(fù)雜度？
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
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（1）

最壞的情況：O（log2N）

為什么是O（log2N)呢？

【畫圖理解】：假設(shè)我們要查找X次，一個數(shù)組的大小是N，每一次二分查找如果沒有找到，N就除以2，考慮最壞的結(jié)果，那么直到N一直除到只剩1為止就結(jié)束了

N/2/2/2/2...=1

2^X=N

X=log2N

數(shù)據(jù)結(jié)構(gòu)之時(shí)間復(fù)雜度-空間復(fù)雜度,數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu),算法,c語言

?可見二分查找算法是一個非常牛逼的算法

N個數(shù)中查找? ? ? ? ? ? ? ? 大概查找次數(shù)

1000? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 10

100W? ? ? ? ? ? ? ? ? ? ? ? ? ? ?20

10億? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 30

但是這個算法的前提是數(shù)組有序

【實(shí)例7】：階乘遞歸的時(shí)間復(fù)雜度:O(N）

遞歸算法時(shí)間復(fù)雜度：遞歸次數(shù)*每次遞歸調(diào)用的次數(shù)

// 計(jì)算階乘遞歸Factorial的時(shí)間復(fù)雜度？
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}

Fac（N)? ?Fac（N-1)? ... Fac（1）

【實(shí)例8】：斐波那契遞歸的時(shí)間復(fù)雜度：O（2^N)

// 計(jì)算斐波那契遞歸Fibonacci的時(shí)間復(fù)雜度？
long long Fibonacci(size_t N)
{
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}

【畫圖理解】：理解遞歸的邏輯思想，每一次遞歸都會調(diào)用小的兩個遞歸，最后右邊的遞歸調(diào)用會先結(jié)束，那么遞歸的次數(shù)就是等比數(shù)列的和減去右下角因提前結(jié)束而缺少的次數(shù)

Fib（N）=2^0+2^1+2^2+...+2^n-X

此處的每次遞歸調(diào)用的次數(shù)是個常數(shù)，就相當(dāng)于沒*

那么大O漸進(jìn)表示法也就是O（2^N)

可見斐波那契數(shù)列的遞歸寫法完全是一個沒有實(shí)際用途的算法，因?yàn)樘?/p>

數(shù)據(jù)結(jié)構(gòu)之時(shí)間復(fù)雜度-空間復(fù)雜度,數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu),算法,c語言

?4.空間復(fù)雜度

空間復(fù)雜度也是一個數(shù)學(xué)表達(dá)式，是一個算法在運(yùn)行過程中的臨時(shí)額外占用存儲空大小的量度

空間復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個也沒有太大的意義，所以空間復(fù)雜度算的是變量的個數(shù)

空間復(fù)雜度計(jì)算規(guī)則基本跟時(shí)間復(fù)雜度類似，也使用大O漸進(jìn)表示法

【注意】:函數(shù)運(yùn)行時(shí)所需要的棧空間（存儲參數(shù)，局部變量，一些存儲器信息等等）在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過函數(shù)在運(yùn)行時(shí)申請額外空間來確定

【實(shí)例1】：冒泡排序的空間復(fù)雜度：O（1）

冒泡排序中有三個變量：exchang，end，i，那么根據(jù)大O漸進(jìn)表示法為O（1）

// 計(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;
}
}

【實(shí)例2】：斐波那契遞歸的空間復(fù)雜度：O（N）

N個數(shù)的數(shù)組，動態(tài)開辟了N+1個空間，簡化過后空間復(fù)雜度為O（N）

這個函數(shù)返回的是斐波那契數(shù)列的前n項(xiàng)的數(shù)組，而不是一個數(shù)

那個函數(shù)的時(shí)間復(fù)雜度為O（N），比遞歸的O（2^N)簡化了很多

// 計(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 ;
}

【實(shí)例3】：函數(shù)階乘遞歸的空間復(fù)雜度：O(N)

// 計(jì)算階乘遞歸Factorial的空間復(fù)雜度？
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}

【畫圖理解】：遞歸函數(shù)調(diào)用了N次，開辟了N個棧幀，每個棧幀使用了常數(shù)的個空間，所以空間復(fù)雜度為O（N）?（只要看遞歸的深度）

數(shù)據(jù)結(jié)構(gòu)之時(shí)間復(fù)雜度-空間復(fù)雜度,數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu),算法,c語言

?【拓展】遞歸版斐波那契數(shù)列的空間復(fù)雜度：O（N）

// 計(jì)算斐波那契遞歸Fibonacci的空間復(fù)雜度？
long long Fibonacci(size_t N)
{
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}

【畫圖理解】：本函數(shù)調(diào)用空間的順序是Fbi（N),Fbi（N-1）...Fbi(1),也就是最左邊的一個枝干，然后這些函數(shù)的空間銷毀，繼續(xù)下一個枝干，這樣函數(shù)遞歸的深度一直都是N，而不會是2^N

空間是可以重復(fù)利用，不累計(jì)的

時(shí)間是一去不復(fù)返，累積的

數(shù)據(jù)結(jié)構(gòu)之時(shí)間復(fù)雜度-空間復(fù)雜度,數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu),算法,c語言

這次數(shù)據(jù)結(jié)構(gòu)之時(shí)間和空間復(fù)雜度的內(nèi)容就到此啦，有什么問題歡迎評論區(qū)或者私信交流，覺得筆者寫的還可以，或者自己有些許收獲的，麻煩鐵汁們動動小手，給俺來個一鍵三連，萬分感謝 !?

數(shù)據(jù)結(jié)構(gòu)之時(shí)間復(fù)雜度-空間復(fù)雜度,數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu),算法,c語言文章來源地址http://www.zghlxwxcb.cn/news/detail-634872.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之時(shí)間復(fù)雜度-空間復(fù)雜度的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！