數(shù)據(jù)結(jié)構(gòu)與算法-創(chuàng)新互聯(lián)

數(shù)據(jù)結(jié)構(gòu)與算法，出發(fā)！

成都創(chuàng)新互聯(lián)公司成都網(wǎng)站建設(shè)按需網(wǎng)站制作，是成都網(wǎng)站建設(shè)公司,為紗窗提供網(wǎng)站建設(shè)服務(wù),有成熟的網(wǎng)站定制合作流程，提供網(wǎng)站定制設(shè)計(jì)服務(wù)：原型圖制作、網(wǎng)站創(chuàng)意設(shè)計(jì)、前端HTML5制作、后臺(tái)程序開發(fā)等。成都網(wǎng)站改版熱線：028-86922220

數(shù)據(jù)結(jié)構(gòu)與算法系列也將持續(xù)更新。

有C語(yǔ)言一定基礎(chǔ)的讀者可以來(lái)學(xué)習(xí)一下數(shù)據(jù)結(jié)構(gòu)與算法~

如果對(duì)C語(yǔ)言還有遺憾或者是想再學(xué)習(xí)一下，請(qǐng)關(guān)注我的C語(yǔ)言初階系列

目錄

什么是數(shù)據(jù)結(jié)構(gòu)？|? 什么是算法？

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

嵌套循環(huán)時(shí)間復(fù)雜度的計(jì)算

雙重循環(huán)的時(shí)間復(fù)雜度的計(jì)算

常數(shù)循環(huán)的時(shí)間復(fù)雜度

strchar的時(shí)間復(fù)雜度

冒泡排序的時(shí)間復(fù)雜度

二分查找的時(shí)間復(fù)雜度

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

斐波那契遞歸的時(shí)間復(fù)雜度

什么是數(shù)據(jù)結(jié)構(gòu)？|? 什么是算法？

在很多地方，數(shù)據(jù)結(jié)構(gòu)總是和算法放在一起叫的。

比如很多課程叫做《數(shù)據(jù)結(jié)構(gòu)與算法》，而不是把它們分成獨(dú)立的課程。

在一些概念中，數(shù)據(jù)結(jié)構(gòu)和算法被這樣定義：

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式，指相互之間存在一定或多種數(shù)據(jù)元素的集合。

算法就是定義良好的計(jì)算過(guò)程，它取一個(gè)或一組的值為輸入，并產(chǎn)生一個(gè)或一組值作為輸出。簡(jiǎn)單來(lái)說(shuō)算法就是一系列的計(jì)算步驟，用來(lái)將輸入數(shù)據(jù)轉(zhuǎn)化成輸出結(jié)果。

看完這些概念，您理解嗎？

形象地來(lái)說(shuō)，數(shù)據(jù)結(jié)構(gòu)就是一些項(xiàng)目在實(shí)現(xiàn)的過(guò)程中，我們可能需要在內(nèi)存中把數(shù)據(jù)給存儲(chǔ)起來(lái)。

比如說(shuō)，要實(shí)現(xiàn)一個(gè)通訊錄，我們要把每個(gè)人的信息去存儲(chǔ)起來(lái)。

那怎么把它們存儲(chǔ)起來(lái)呢？

如果學(xué)習(xí)過(guò)C語(yǔ)言就知道要用數(shù)組存儲(chǔ)。

除了數(shù)組之外，還可以以鏈表、樹、哈希表的形式存儲(chǔ)......

不論是哪種形式，都有其特點(diǎn)。

用數(shù)組存儲(chǔ)，它的優(yōu)點(diǎn)就是很方便，缺點(diǎn)就是假如你數(shù)組有500個(gè)元素，那么存儲(chǔ)過(guò)500個(gè)人的信息后就不能再存儲(chǔ)了。

雖然C99標(biāo)準(zhǔn)可以使用動(dòng)態(tài)數(shù)組，但還需要給數(shù)組擴(kuò)容，比較麻煩。

而使用鏈表的話會(huì)更方便。只需要申請(qǐng)內(nèi)存，然后用指針鏈接起來(lái)即可。

如果我們想去查找某個(gè)人，就可能要用到樹了。日后細(xì)講。

所以我們就要根據(jù)需求去選擇不同的數(shù)據(jù)結(jié)構(gòu)，要去考慮用那種數(shù)據(jù)結(jié)構(gòu)更合適。

算法有很多很多，如排序、查找、去重。

這些天手機(jī)圈有很多驚喜，榮耀發(fā)布了MgicOS、小米13對(duì)標(biāo)iPhone等等......

如果我想買一部手機(jī)，想買最貴的，我就需要用價(jià)格去降序排序，想買最新發(fā)布的，就要根據(jù)時(shí)間去排序，想看一下大家買的比較多的，就要根據(jù)銷量去排序。

這就用到了排序算法。

還有很多很高級(jí)的算法，比如推薦算法。

刷短視頻，短視頻平臺(tái)會(huì)根據(jù)你的偏好去推薦相關(guān)的視頻。

數(shù)據(jù)結(jié)構(gòu)和算法已經(jīng)在日常生活中無(wú)處不在了。

要設(shè)計(jì)算法，很多時(shí)候就要用到數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)和算法是不分家的，有些數(shù)據(jù)結(jié)構(gòu)需要用到算法，有些算法需要用到數(shù)據(jù)結(jié)構(gòu)。

什么是數(shù)據(jù)結(jié)構(gòu)？什么是算法？筆者之所以把這兩個(gè)問(wèn)題放在一塊，就是因?yàn)樗鼈兟?lián)系太緊密了。

在C語(yǔ)言階段練習(xí)和總結(jié)并重，而在數(shù)據(jù)結(jié)構(gòu)階段更側(cè)重好好寫代碼，還要學(xué)會(huì)畫圖和分析。

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

算法分析分為兩個(gè)方面，一個(gè)是時(shí)間復(fù)雜度，另一個(gè)是空間復(fù)雜度。本節(jié)重點(diǎn)講解時(shí)間復(fù)雜度。

對(duì)于一個(gè)算法，我們要去判斷它的運(yùn)行的好壞，最重要的是看它運(yùn)行起來(lái)跑得快不快，除此之外還要看它占用多少空間。

時(shí)間復(fù)雜度主要衡量一個(gè)算法的運(yùn)行快慢，空間復(fù)雜度主要衡量一個(gè)算法運(yùn)行所需要的額外的空間。

早期的時(shí)候還比較關(guān)注空間，而現(xiàn)在基本上不關(guān)注空間了，因?yàn)楝F(xiàn)在內(nèi)存越來(lái)越大了，能夠滿足內(nèi)存占用較多的程序運(yùn)行。

但是算法對(duì)時(shí)間還有一定的追求。

算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，但注意這里所指的函數(shù)是數(shù)學(xué)中的帶有未知數(shù)的函數(shù)表達(dá)式。

時(shí)間復(fù)雜度不去計(jì)算它能跑多少秒，因?yàn)橐粋€(gè)程序在配置很低的機(jī)器上和配置很高的機(jī)器上的時(shí)間是不一樣的。

環(huán)境不同，具體運(yùn)行時(shí)間不同。

算法中的基本操作的執(zhí)行次數(shù)，是算法的時(shí)間復(fù)雜度。

嵌套循環(huán)時(shí)間復(fù)雜度的計(jì)算

下面來(lái)計(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);
}

準(zhǔn)確的次數(shù)是n^2+2n+10;

時(shí)間復(fù)雜度的函數(shù)式為

F(N)=N*N+2*N+10

我們看下這張圖：

如果我們把F(N)=N*N+2*N+10簡(jiǎn)化一下，簡(jiǎn)化成F(N)=N*N

那么

N=10時(shí)， 復(fù)雜度為100

N=100時(shí)，復(fù)雜度為10000

N=1000時(shí)，復(fù)雜度為1000000

可以發(fā)現(xiàn)，N越大，后兩項(xiàng)對(duì)結(jié)果的影響越小。

實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí)，我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)。

這就好比求極限，看下邊這道題：

當(dāng)x趨于無(wú)窮大時(shí)，(x^2-1)/(2x^2-x-1)~1/2。

計(jì)算時(shí)間復(fù)雜度就好比求極限，在F(N)=N*N+2*N+10中，因?yàn)楫?dāng)N足夠大時(shí)，后邊式子對(duì)復(fù)雜度的影響越來(lái)越小，那我們就把它化簡(jiǎn)成F(N)=N*N。

這里我們使用大O的漸進(jìn)表示法。大O的漸進(jìn)表示法就是估算。

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

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

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

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

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

那么就得出此算法的時(shí)間復(fù)雜度為O(N^2)。

雙重循環(huán)的時(shí)間復(fù)雜度的計(jì)算

請(qǐng)計(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);
}

精確的計(jì)算是2N+10。

那么當(dāng)N無(wú)限大的時(shí)候，10對(duì)結(jié)果的影響很小。而當(dāng)N無(wú)限大的時(shí)候N和2N是同一個(gè)級(jí)別。

在上文也提到如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。

所以可得出O(N)。

再來(lái)一道題，請(qǐng)計(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);
}

結(jié)果為O(M+N)。

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

M和N都是未知數(shù)，但是我們不知道是M大還是N大。

所以M和N都要用。

如果這道題有了條件：

如果條件是M遠(yuǎn)大于N，那么結(jié)果為O(M)；

如果條件是N遠(yuǎn)大于M，那么結(jié)果為O(N)；

如果條件是M和N差不多大，那么既可以用O(M)表示，也可以用O(N)表示。

常數(shù)循環(huán)的時(shí)間復(fù)雜度

請(qǐng)計(jì)算Func2的時(shí)間復(fù)雜度

void Func4(int N)
{
    int count = 0;
    for (int k = 0; k< 100; ++k)
    {
        ++count;
    }
    printf("%d\n", count);
}

這里沒(méi)有未知數(shù)，那就是100次。

根據(jù)推導(dǎo)大O階的方法用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)，那么這道題的時(shí)間復(fù)雜度就是O(1)。

如果有人要求你把某個(gè)算法優(yōu)化到O(1)，這并不意味著只讓算法執(zhí)行一次，而是運(yùn)行常數(shù)次。

strchar的時(shí)間復(fù)雜度

請(qǐng)計(jì)算strchar的時(shí)間復(fù)雜度：

const char* strchr(const char* str, int character);

這是一個(gè)庫(kù)函數(shù)，不怎么常用的庫(kù)函數(shù)，它的代碼大概如下：

while (*str)
{
    if (*str == character)
        return str;
    else
        ++str;
}

它的功能是在字符串里查找一個(gè)字符。

那么它的時(shí)間復(fù)雜度是多少？

假設(shè)我從“hello world”中查找字符：

假設(shè)我查找的是字符是h? ?----> ?O(1)

假設(shè)我查找的是字符是w? ?----> ?O(N/2)

假設(shè)我查找的是字符是d? ?----> ?O(N)

（我們不知道字符串的長(zhǎng)度，那就用N。

那么這三種情況分別對(duì)應(yīng)最好的情況、平均的情況、最壞的情況。

有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況：

最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界)

平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)

最壞情況：任意輸入規(guī)模的大運(yùn)行次數(shù)(上界)

當(dāng)一個(gè)算法隨著輸入不同，時(shí)間復(fù)雜度不同，時(shí)間復(fù)雜度做悲觀預(yù)期，看最壞情況。

我們一般最看重最壞的情況。只有極個(gè)別少數(shù)算法不需要考慮最壞和平均情況。

99%情況下都是看最壞情況！

冒泡排序的時(shí)間復(fù)雜度

請(qǐng)計(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;
    }
}

先算一個(gè)精確的，F(xiàn)(N)=(1+N)/2。

為什么是F(N)=(1+N)/2？

我們要去了解下冒泡排序的思想。有的算法不能只看代碼。

我們做最悲觀的考慮，那么每個(gè)數(shù)都參與了比較。

圖中紅色代表未比較過(guò)的數(shù)據(jù)，黃色方框代表已經(jīng)排好序的數(shù)據(jù)，藍(lán)色線條代表比較次數(shù)。

從最右邊執(zhí)行過(guò)的次數(shù)可以發(fā)現(xiàn)，比較的總次數(shù)為(N-1)+(N-2)+(N-3)+···+1。

這是個(gè)等差數(shù)列，循環(huán)了N-1次，比較了(N-1)+(N-2)+(N-3)+···+1次。

也就是說(shuō)項(xiàng)數(shù)為N-1，那么總次數(shù)為N*(N-1)/2。

它的時(shí)間復(fù)雜度為O(N^2)。

二分查找的時(shí)間復(fù)雜度

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

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

如果只去看幾層循環(huán)，那么它的時(shí)間復(fù)雜度就是O(N)，然而這是錯(cuò)的！

它的時(shí)間復(fù)雜度是O(\frac{}{}log2N)。

關(guān)于二分查找的思想詳見我之前的博客http://t.csdn.cn/kIg93

二分查找最好的情況是O(1)，就是你要查找的數(shù)正好在中間。

事實(shí)上我們一般不關(guān)注最好情況，那么最壞情況是多少？

找不到是最壞的情況。

假設(shè)我們要查找X次也沒(méi)找到，那么2^X=N。

可知X=log2N

二分查找是一個(gè)非常厲害的算法。

在1000個(gè)數(shù)中查找，大概需要10次；

在100w個(gè)數(shù)中查找，大概需要20次；

在10億個(gè)數(shù)中查找，大概需要30次。

可以發(fā)現(xiàn)隨著N急劇增大，需要查找的次數(shù)變化并不是特別明顯。

用時(shí)間復(fù)雜度分析二分查找，才知道二分查找的神奇之處。

假設(shè)我們從14億人中找一個(gè)人，最多需要31次（前提是排好序了......）。

在有序的前提下，二分查找是一個(gè)很厲害的算法。

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

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

long long Fac(size_t N)
{
    if (0 == N)
        return 1;
    return Fac(N - 1) * N;
}

遞歸算法：遞歸次數(shù)*每次遞歸調(diào)用的次數(shù)。

遞歸次數(shù)好理解，那么每次遞歸調(diào)用的次數(shù)是什么？

比如if判斷是一次，然后return后邊的Fac里的計(jì)算是一次......但是這些都可以理解為常數(shù)次！

所以關(guān)注遞歸次數(shù)就好。

那么該算法的時(shí)間復(fù)雜度就是O(N)。

斐波那契遞歸的時(shí)間復(fù)雜度

計(jì)算斐波那契遞歸Fib的時(shí)間復(fù)雜度：

long long Fib(size_t)
{
    if (N< 3)
        return 1;
    return Fib(N - 1) + Fib(N - 2);
}

我們來(lái)看斐波那契遞歸的過(guò)程：

可以發(fā)現(xiàn)，右邊比左邊更早地完成了遞歸。

但是當(dāng)N足夠大時(shí)，右邊比左邊少遞歸的次數(shù)X對(duì)整體遞歸次數(shù)的影響很小。

我們之前提到過(guò)：

遞歸算法：遞歸次數(shù)*每次遞歸調(diào)用的次數(shù)。

由于遞歸內(nèi)調(diào)用次數(shù)可以理解為常數(shù)，那么

Fib(N)=2^0+2^1+2^3+······+2^(n-2)+2^(n-1)-X

不過(guò)X可以忽略不計(jì)，因?yàn)閄前邊的次數(shù)和遠(yuǎn)大于X。

那么用等比數(shù)列計(jì)算可得到

Fib(N)=2^N-1

1也可以忽略不計(jì)，所以時(shí)間復(fù)雜度為

O(2^N)

創(chuàng)作不易，這次碼了將近五千字，求各位老鐵三連支持下！

你是否還在尋找穩(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)查看詳情吧

當(dāng)前名稱：數(shù)據(jù)結(jié)構(gòu)與算法-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://www.muchs.cn/article32/epdsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、品牌網(wǎng)站制作、關(guān)鍵詞優(yōu)化、移動(dòng)網(wǎng)站建設(shè)、響應(yīng)式網(wǎng)站、商城網(wǎng)站

廣告

聲明：本網(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)

成都seo排名網(wǎng)站優(yōu)化