空間復(fù)雜度計(jì)算超全整理！?。ㄒ黄鹗炙簭?fù)雜度計(jì)算-創(chuàng)新互聯(lián)

創(chuàng)新互聯(lián)專注于寶應(yīng)企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站,商城網(wǎng)站定制開(kāi)發(fā)。寶應(yīng)網(wǎng)站建設(shè)公司,為寶應(yīng)等地區(qū)提供建站服務(wù)。全流程按需求定制開(kāi)發(fā)，專業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)

承接上文：算法效率與時(shí)間復(fù)雜度(8條消息) 時(shí)間復(fù)雜度計(jì)算超全整理！！（數(shù)據(jù)結(jié)構(gòu)和算法的第一步_vpurple__的博客-博客

---

目錄

0.前言

1.空間復(fù)雜度

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

1.2舉幾個(gè)計(jì)算空間復(fù)雜度的例子

1.2.1 計(jì)算冒泡排序的空間復(fù)雜度

1.2.1計(jì)算階乘遞歸的時(shí)間復(fù)雜度

1.2.3計(jì)算用數(shù)組實(shí)現(xiàn)還有用變量實(shí)現(xiàn)的斐波拉契數(shù)列的空間復(fù)雜度

1.2.4計(jì)算用遞歸實(shí)現(xiàn)的斐波拉契數(shù)的空間復(fù)雜度

2.常見(jiàn)復(fù)雜度的對(duì)比

---

---

0.前言

相比而言現(xiàn)在算法不那么關(guān)注空間復(fù)雜度，因?yàn)楝F(xiàn)在的設(shè)備的存儲(chǔ)空間都比較大。

1GB=1024*1024*1024字節(jié)? ?

1GB 大概是10億字節(jié)

1MB 大概是100萬(wàn)字節(jié)

1GB=1024MB? ?1MB=1024KB? ?1KB=1024字節(jié)

---

1.空間復(fù)雜度

空間復(fù)雜度也是一個(gè)數(shù)學(xué)表達(dá)式，是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度 ，也就是額外占取的空間的大小。

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

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

注意：函數(shù)運(yùn)行時(shí)所需要的?？臻g(存儲(chǔ)參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過(guò)函數(shù)在運(yùn)行時(shí)候顯式申請(qǐng)的額外空間來(lái)確定。

---

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

大O符號(hào)（Big O notation）：是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)。

O()括號(hào)里面的數(shù)更多的表達(dá)的是這個(gè)算法的量級(jí)，大O是一個(gè)估算，并不是準(zhǔn)確的執(zhí)行次數(shù)。

推導(dǎo)大O階方法：

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

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

3、如果最高階項(xiàng)系數(shù)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階。

---

1.2舉幾個(gè)計(jì)算空間復(fù)雜度的例子 1.2.1 計(jì)算冒泡排序的空間復(fù)雜度

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

分析如下：

1.2.1計(jì)算階乘遞歸的時(shí)間復(fù)雜度

// 計(jì)算階乘遞歸Fac的空間復(fù)雜度？
long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 
 return Fac(N-1)*N;
}

階乘遞歸的時(shí)間復(fù)雜度：O(N).

分析如下：

1.2.3計(jì)算用數(shù)組實(shí)現(xiàn)還有用變量實(shí)現(xiàn)的斐波拉契數(shù)列的空間復(fù)雜度

// 計(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ù)組實(shí)現(xiàn)斐波拉契數(shù)列的空間復(fù)雜度：O(N).

用三個(gè)變量來(lái)回計(jì)算斐波拉契數(shù)列的空間復(fù)雜度是：O(N).

1.2.4計(jì)算用遞歸實(shí)現(xiàn)的斐波拉契數(shù)的空間復(fù)雜度

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

用遞歸實(shí)現(xiàn)的斐波拉契數(shù)的空間復(fù)雜度：O(N).

先計(jì)算一下在主函數(shù)中重復(fù)調(diào)用兩個(gè)函數(shù)，函數(shù)所占用的空間大小。

空間是可以重復(fù)利用的。

把空間還給操作系統(tǒng)，釋放了，而不是銷毀了，只是把使用權(quán)交給操作系統(tǒng)了

空間復(fù)雜度基本上是O(1)或者O(N)，其它的空間復(fù)雜度不常見(jiàn)。假設(shè)開(kāi)一個(gè)N*N的數(shù)組，那么它的空間復(fù)雜度是O(N^2)。結(jié)構(gòu)體不討論結(jié)構(gòu)體個(gè)數(shù)，只看整體。不看具體，只看量級(jí)。

---

2.常見(jiàn)復(fù)雜度的對(duì)比

一般算法常見(jiàn)的復(fù)雜度如下：

表格越往下復(fù)雜度相對(duì)越高

5201314	O(1)	常數(shù)階
3log(2)n+4	O(log(2)n)	對(duì)數(shù)階
3n+4	O(n)	線性階
2n+3nlog(2)n+14	O(nlog(2)n)	nlogn階
3n^2+4n+5	O(n^2)	平方階
4n^3+3n^2+4n+5	O(n^3)	立方階
2^n	O(2^n)	指數(shù)階

圖例如下所示（圖片來(lái)源于百度）：

請(qǐng)注意：與 logN 是等價(jià)的。

---

你好！這里是媛仔，希望這篇對(duì)于空間復(fù)雜度的總結(jié)對(duì)你有所幫助，可以關(guān)注我的專欄《數(shù)據(jù)結(jié)構(gòu)進(jìn)階之路———努力版》，這個(gè)專欄之后也會(huì)同步更新數(shù)據(jù)結(jié)構(gòu)相關(guān)內(nèi)容，希望對(duì)你有所幫助，也希望可以與大家多多交流，共同進(jìn)步??！祝你天天開(kāi)心^-^，媛仔去肝下一篇啦~~

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：空間復(fù)雜度計(jì)算超全整理?。。ㄒ黄鹗炙簭?fù)雜度計(jì)算-創(chuàng)新互聯(lián)
文章來(lái)源：http://muchs.cn/article4/dhegie.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、ChatGPT、網(wǎng)站收錄、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈、外貿(mào)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)