?

目錄

前言：

1.算法

1.1算法的特性

1.2設(shè)計(jì)算法

2.空間復(fù)雜度

3.學(xué)習(xí)復(fù)雜度的意義

?博主CSDN：啊蘇要學(xué)習(xí)

? ? ?專欄分類：數(shù)據(jù)結(jié)構(gòu)?

? 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是一件有趣的事情，希望讀者能在我的博文切實(shí)感受到數(shù)據(jù)之間存在的關(guān)系，在對數(shù)據(jù)元素進(jìn)行操作的時(shí)候，能心中有數(shù)，腦中有畫！?

?

前言：

? 在前面我們已經(jīng)講過時(shí)間復(fù)雜度了，空間復(fù)雜度也幾乎是八九不離十，我們這節(jié)主要來講講一個(gè)好的算法需要滿足什么樣的特點(diǎn)。

1.算法

? 算法實(shí)際上就是一組一組的操作，在計(jì)算機(jī)上表現(xiàn)為一組指令，讓計(jì)算機(jī)按照我們想要的邏輯進(jìn)行運(yùn)算，并能有效的解決實(shí)際問題。

1.1算法的特性

? 算法具有五個(gè)特性，輸入和輸出、有限性和可行性以及確定性。

• ? 輸入和輸出是提供數(shù)據(jù)和返回結(jié)果的代名詞，一個(gè)算法可以沒有輸入，也可以有多個(gè)輸入，取決于具體需求。但輸出是必須有的，如果一個(gè)算法沒有將其計(jì)算的結(jié)果返給我們使用，那還要這個(gè)算法干嘛呢？
• 有限性指的是實(shí)現(xiàn)解決問題算法的指令是有限的，執(zhí)行完后自動會結(jié)束程序，并且條指令，每個(gè)步驟所用的時(shí)長都在可以接收的時(shí)間內(nèi)。

• 可行性是指在實(shí)現(xiàn)算法的整個(gè)過程中，每一個(gè)步驟的是合理、可以實(shí)現(xiàn)的、也就是不會出錯(cuò)，可以得到正確的結(jié)果。
• 確定性，算法的每一個(gè)步驟只能有一種結(jié)果，不管在什么樣的環(huán)境下、在什么編譯器上，運(yùn)行算出來的結(jié)果是唯一的。

1.2設(shè)計(jì)算法

? 1.設(shè)計(jì)算法，需要我們能夠正確的表達(dá)邏輯，以解決實(shí)際問題，這個(gè)要求我們對算法的設(shè)計(jì)要有正確性。

? 算法的正確性：指算法具有完整的結(jié)構(gòu)，包括輸入、輸出、和加工處理數(shù)據(jù)的過程中是唯一性的，最終能夠得到正確的答案。

? 算法正確的四大層次：

1. 算法程序沒有語法上的錯(cuò)誤（沒有語法錯(cuò)誤時(shí)最基礎(chǔ)的）
2. 算法對于合理數(shù)據(jù)的輸入能夠得出正確的結(jié)果
3. 算法能對不恰當(dāng)?shù)臄?shù)據(jù)輸入返回令人滿意的信息反饋（而不是輸入不合理的數(shù)據(jù)后就跑出一些隨意的值）
4. 算法對精心挑選的具有鉆牛角尖性質(zhì)的數(shù)據(jù)仍能處理得出滿足要求的輸入結(jié)果。

? 對于這四種境界，層次1是最低端的，層次4在一般情況下是很難達(dá)到的，我們退而求其次，第3層是能滿足大部分要求并且被我們當(dāng)成是算法是否正確的標(biāo)準(zhǔn)。

? 算法的可讀性：算法設(shè)計(jì)，不是為了讓人讀不懂，而是為了具有可讀性，便于交流，以及后期的維護(hù)。

? 一個(gè)算法，如果只能給敲這段代碼的人和計(jì)算機(jī)理解，那么從技術(shù)角度上來看，可能這個(gè)人是大神，別人看不懂，要不就是敲的令人看不懂。一般沒注釋的代碼，都需要花費(fèi)別人很多時(shí)間去理解。我們不追求花里胡哨，簡單易懂，質(zhì)量高的代碼才是我們追求的！

? 算法的健壯性：當(dāng)輸入的數(shù)據(jù)不合理的時(shí)候，會有特殊的情況處理，要么是給程序員提示出錯(cuò)，要么拋出異常報(bào)錯(cuò)。而不是編寫的代碼隱晦性的存在錯(cuò)誤，但不是致命的，單獨(dú)跑沒問題，當(dāng)在工程里將代碼合在一起的時(shí)候，跑起來程序就掛了，這時(shí)要找錯(cuò)誤那簡直是程序員噩夢。

? 算法的時(shí)間效率高、存儲量低：算法的時(shí)間復(fù)雜度要盡可能的小，時(shí)間效率要追求高。存儲量低，不希望算法在執(zhí)行的時(shí)候?qū)?nèi)存空間的開銷太多。

? 算法的特性和算法的設(shè)計(jì)怎么記？我們這樣記：算法設(shè)計(jì)里有個(gè)正確性，這個(gè)正確性要求算法是一個(gè)完整的算法。那么就要有輸入輸出，結(jié)果要想正確，計(jì)算過程肯定是唯一的，我們怎么得出結(jié)果是正確的呢？那是因?yàn)樗惴ň哂杏邢扌?計(jì)算機(jī)在短時(shí)間內(nèi)跑的出結(jié)果讓我們看到是正確的)和可行性(在計(jì)算機(jī)中可以實(shí)現(xiàn))。

? 博主相信讀者多看幾遍，算法的特性就記下來了~，而算法設(shè)計(jì)的要求其實(shí)比較容易理解滴。

2.空間復(fù)雜度

? 前面我們講過算法的時(shí)間復(fù)雜度，這里我們補(bǔ)充一下算法的空間復(fù)雜度。

? 鏈接：時(shí)間復(fù)雜度

? 在以前，計(jì)算機(jī)的內(nèi)存是很小的，內(nèi)存很珍貴，當(dāng)時(shí)考慮的更多是空間復(fù)雜度，現(xiàn)在存儲空間是足夠了的，我們追求的是時(shí)間上的效率， 當(dāng)然空間開銷小也是需要的，畢竟在大數(shù)據(jù)時(shí)代，即使內(nèi)存變多了，也不是讓我們來浪費(fèi)的理由。

? 空間復(fù)雜度：并不是算占用的字節(jié)數(shù)，而是算創(chuàng)建變量的個(gè)數(shù)。

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;
}

? 這里我們看看創(chuàng)建了多少個(gè)變量，形參部分有整型指針a、整型變量n，還有size_t類型end變量、size_t類型i變量、整型變量exchange變量總共五個(gè)。是常數(shù)，所以空間復(fù)雜度是O(1)。

? 空間復(fù)雜度和時(shí)間復(fù)雜度的都是同樣用大O漸進(jìn)表示法。

? exchange在進(jìn)入循環(huán)時(shí)創(chuàng)建，出了循環(huán)時(shí)被銷毀。在這個(gè)重復(fù)的過程中，是不是應(yīng)該像計(jì)算時(shí)間復(fù)雜度那樣按次數(shù)來算空間中變量的創(chuàng)建次數(shù)嗎？不是的，次數(shù)在時(shí)間上有累計(jì)，在空間上不累計(jì)。

? 空間復(fù)雜度是在創(chuàng)建最多額外變量時(shí)候，變量的個(gè)數(shù)才是空間復(fù)雜度的數(shù)，也就是要在變量最多的時(shí)候，計(jì)算這個(gè)時(shí)候占的空間多少。

long long* Fib(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;
}

? 計(jì)算斐波那契數(shù)列的空間復(fù)雜度：size_t n 是一個(gè)變量，malloc開辟了n+1個(gè)元素的數(shù)組大小，? ? int i也是一個(gè)變量，這里面總共的變量數(shù)是N+3。大O表示法，對空間復(fù)雜度貢獻(xiàn)值最大的是N，所以空間復(fù)雜度是O(N)。

? 一般情況下，我們都是開辟常數(shù)個(gè)變量或是開辟N個(gè)元素的數(shù)組，對應(yīng)的空間復(fù)雜度是O(1)和O(N)。

? 用遞歸求階乘的空間復(fù)雜度：

? 在算階乘的時(shí)候，我們求N的階乘，就需要調(diào)用N次函數(shù)，每次函數(shù)都會創(chuàng)建常量個(gè)變量，最終空間復(fù)雜度為O(N)。

? 注意：所有的空間在程序結(jié)束后歸還操作系統(tǒng)；在往下遞歸的時(shí)候，前面的函數(shù)還沒結(jié)束，信息仍保留著，只有在回歸，回溯的時(shí)候才一個(gè)一個(gè)銷毀。

3.學(xué)習(xí)復(fù)雜度的意義

? 不管是時(shí)間復(fù)雜度也好，空間復(fù)雜度也罷。我們?yōu)槭裁匆獙W(xué)這些東西，我只要能寫出代碼，能跑起出正確結(jié)果就OK了，學(xué)這個(gè)干嘛？如果你在問這個(gè)，只能說你對還沒在玩"計(jì)算機(jī)"。

• 首先，我們在刷題的時(shí)候，經(jīng)常會有時(shí)間復(fù)雜度的限制、空間復(fù)雜度的限制。學(xué)完后我們就懂題目應(yīng)該怎么做
• 其次，學(xué)完這些復(fù)雜度能夠促進(jìn)我們思考更好的算法，解決現(xiàn)有的效率低，占用存儲量大的算法，在這探索的過程中開拓新思維，相當(dāng)于在玩的感覺。

? OK，學(xué)到這里，我們對數(shù)據(jù)結(jié)構(gòu)里的基礎(chǔ)知識都掌握了，接下來的數(shù)據(jù)結(jié)構(gòu)知識主要是寫代碼題了，跟博主一起學(xué)吧！

結(jié)語：希望讀者讀完能有所收獲！對數(shù)據(jù)結(jié)構(gòu)有進(jìn)一步的認(rèn)識！?

? 讀者對本文不理解的地方，或是發(fā)現(xiàn)文章內(nèi)容上有誤等，請?jiān)谙路皆u論留言告訴博主喲~，也可以對博主提出一些文章改進(jìn)的建議，感激不盡！最后的最后！

? ?求點(diǎn)贊，求關(guān)注，你的點(diǎn)贊是我更新的動力，一起進(jìn)步吧。文章來源地址http://www.zghlxwxcb.cn/news/detail-463144.html

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