從頭開始：數(shù)據(jù)結(jié)構(gòu)和算法入門（時間復(fù)雜度、空間復(fù)雜度）

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

?文章來源地址http://www.zghlxwxcb.cn/news/detail-625387.html

文章目錄

前言

1.算法效率

1.1 如何衡量一個算法的好壞

1.2 算法的復(fù)雜度

2.時間復(fù)雜度?

2.1 時間復(fù)雜度的概念

2.2 大O的漸進表示法

2.3常見時間復(fù)雜度計算

3.空間復(fù)雜度

4.常見復(fù)雜度對比

總結(jié)

前言

????????C語言的學(xué)習(xí)篇已經(jīng)結(jié)束，今天開啟新的篇章——數(shù)據(jù)結(jié)構(gòu)和算法。本期主要內(nèi)容是對數(shù)據(jù)結(jié)構(gòu)和算法入門知識——復(fù)雜度進行講解。

1.算法效率

1.1 如何衡量一個算法的好壞

如何衡量一個算法的好壞呢？比如對于以下斐波那契數(shù)列：

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

?這個斐波那契數(shù)列的遞歸實現(xiàn)方式非常簡潔，但簡潔一定好嗎？那該如何衡量算法好與壞呢？

?答案是，一個程序中算法的復(fù)雜度，才是衡量一個程序好壞的標準。

?1.2 算法的復(fù)雜度

????????算法在編寫成可執(zhí)行程序后，運行時需要耗費時間資源和空間(內(nèi)存)資源。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復(fù)雜度和空間復(fù)雜度。

????????時間復(fù)雜度主要衡量一個算法的運行快慢，而空間復(fù)雜度主要衡量一個算法運行所需要的額外空間。

????????在計算機發(fā)展的早期，計算機的存儲容量很小。所以對空間復(fù)雜度很是在乎。但是經(jīng)過計算機行業(yè)的迅速發(fā)展，計算機的存儲容量已經(jīng)達到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個算法的空間復(fù)雜度。

算法的復(fù)雜度在校招中也是極為重要的考察點。

2.時間復(fù)雜度?

2.1 時間復(fù)雜度的概念

時間復(fù)雜度的定義：

????????在計算機科學(xué)中，算法的時間復(fù)雜度是一個函數(shù)，它定量描述了該算法的運行時間。

????????一個算法執(zhí)行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復(fù)雜度這個分析方式。一個算法所花費的時間與其中語句的執(zhí)行次數(shù)成正比，算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復(fù)雜度。

?????????找到某條基本語句與問題規(guī)模N之間的數(shù)學(xué)表達式，就是算出了該算法的時間復(fù)雜度。來看一下下面這段代碼：

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ù)：

N = 10 ，F(xiàn)(N) = 130
N = 100 ，F(xiàn)(N) = 10210
N = 1000， F(N) = 1002010

????????它們的關(guān)系式： F（N）=N*N+2*N+10，我們發(fā)現(xiàn)隨著N的增大，2*N和10對執(zhí)行次數(shù)的影響在逐漸減小。

????????實際中我們計算時間復(fù)雜度時，我們其實并不一定要計算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進表示法。

?2.2 大O的漸進表示法

大O符號：是用于描述函數(shù)漸進行為的數(shù)學(xué)符號。

?推導(dǎo)大O階的基本方法：

用常數(shù)1取代運行時間中的所有加法常數(shù)（任何常數(shù)，有確切數(shù)字且不超int最大范圍都算）。
在修改后的運行次數(shù)函數(shù)中，只保留最高階項。
如果最高階項存在且不是1，則去除與這個項目相乘的常數(shù)。得到的結(jié)果就是大O階（如果有常數(shù)項除去常數(shù)項）

?????????使用大O的漸進表示法以后，F(xiàn)unc1的時間復(fù)雜度為N平方。

N = 10，?F(N) = 100
N = 100 ，F(xiàn)(N) = 10000
N = 1000 ，F(xiàn)(N) = 1000000

????????通過上面我們會發(fā)現(xiàn)大O的漸進表示法去掉了那些對結(jié)果影響不大的項，簡潔明了的表示出了執(zhí)行次數(shù)。?

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

最壞情況：任意輸入規(guī)模的最大運行次數(shù)(上界)
平均情況：任意輸入規(guī)模的期望運行次數(shù)
最好情況：任意輸入規(guī)模的最小運行次數(shù)(下界)

例如在一個有N個數(shù)據(jù)的數(shù)組當中，查找一個數(shù)字X：

??最好情況：1次找到
??最壞情況：N次找到
??平均情況：N/2次找到

?????????在實際中一般情況關(guān)注的是算法的最壞運行情況，所以數(shù)組中搜索數(shù)據(jù)時間復(fù)雜度為O(N)

?2.3常見時間復(fù)雜度計算

例1：

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

?這個代碼的時間復(fù)雜度是多少呢？

?Func2基本操作執(zhí)行了2N+10次，通過推導(dǎo)大O階方法知道，時間復(fù)雜度為 O(N)

?例2：

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

?這個程序的時間復(fù)雜度是多少呢？

Func3基本操作執(zhí)行了M+N次，由于M和N都是未知，所以時間復(fù)雜度為 O(N+M)

?例3：

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

?計算該程序的時間復(fù)雜度

?Func4基本操作執(zhí)行了100次，通過推導(dǎo)大O階方法，時間復(fù)雜度為 O(1)

?

?例4：

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ù)雜度是多少？

? ? ? ? 冒泡排序是相鄰兩元素進行比較，再進行交換排序。并且交換的比較的次數(shù)依次減少。冒泡詳細過程可參考下邊博客，其中有對冒泡排序詳細過程介紹。——冒泡排序詳細過程

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

?????????排序一個數(shù)最多需要比較并交換執(zhí)行n-1次，第二個數(shù)需要進行n-2次，……直到排序結(jié)束，總的執(zhí)行次數(shù)也就是等差數(shù)列的和。根據(jù)等差數(shù)列求和公式我們可以得出：最壞執(zhí)行了(N*(N+1)/2次。通過推導(dǎo)大O階方法+時間復(fù)雜度一般看最壞，所以冒泡排序的時間復(fù)雜度為 O(N^2)。

?例5：

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-1;
        else
            return mid;
}

?我們來看一看二分查找的時間復(fù)雜度。

二分查找詳細介紹可參考文章：這就是二分查找？

?二分查找每次將查找區(qū)間進行折半。

從頭開始：數(shù)據(jù)結(jié)構(gòu)和算法入門（時間復(fù)雜度、空間復(fù)雜度）,算法,數(shù)據(jù)結(jié)構(gòu),經(jīng)驗分享,其他 N

N/2

N/2/2

N/2/2/2

……

N/2/2……/2=1；

最壞情況：查找區(qū)間縮放只剩一個數(shù)時。

最壞情況下查找了多少次？除了多少次2，就查找了多少次。

?我們假設(shè)查找了x次，2^x=N，x等于log2(N）,時間復(fù)雜度是算法中的基本操作的執(zhí)行次數(shù)。

?????????操作執(zhí)行最好1次，最壞O(logN)次，時間復(fù)雜度為 O(logN) ，ps：logN在算法分析中表示是底數(shù)為2，對數(shù)為N。有些地方會寫成lgN。（建議通過折紙查找的方式講解logN是怎么計算出來的）。? ? ??

例6：

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

?接下來我們來看看遞歸的時間復(fù)雜度是多少？

????????這個遞歸的時間復(fù)雜度是O(N)，為什么？我們知道遞歸是調(diào)用自身函數(shù)，通過觀察我們發(fā)現(xiàn)，遞歸函數(shù)中只執(zhí)行一次，但是遞歸調(diào)用函數(shù)調(diào)用了N+1次，時間復(fù)雜度是算法中的基本操作的執(zhí)行次數(shù)。調(diào)用了N+1次，就執(zhí)行了N+1次，所以時間復(fù)雜度是O(N)。通過遞歸我們會找到這樣的規(guī)律：遞歸算法的時間復(fù)雜度是多少次調(diào)用的次數(shù)累加。我們知道了這個規(guī)律，那我們再來看看這個遞歸。

?例7：

long long Fac(size_t N)
{
    if(0 == N)
        return 1;
    for(size_t i=0;i<N;i++)
    {
        ……
    }
    return Fac(N-1)*N;
}

?這個遞歸的時間復(fù)雜度是多少？

????????答案是O(N^2)，這里遞歸調(diào)用了N次，但每次調(diào)用都執(zhí)行N次的循環(huán)，注意這里的N是逐漸變小的（每次調(diào)用傳遞的是N-1），所以這個遞歸的執(zhí)行次數(shù)也就是等差數(shù)列的和，我們需要記住，執(zhí)行次數(shù)為等差數(shù)列的和，時間復(fù)雜度就是O(N^2)。我們繼續(xù)來看看這個遞歸。

例8：

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

它的時間復(fù)雜度是多少？

????????它的時間復(fù)雜度是O(2^N)。遞歸算法的時間復(fù)雜度是多少次調(diào)用的次數(shù)累加。這個遞歸是雙路遞歸，它的遞歸路線是成樹狀結(jié)構(gòu)的：

從頭開始：數(shù)據(jù)結(jié)構(gòu)和算法入門（時間復(fù)雜度、空間復(fù)雜度）,算法,數(shù)據(jù)結(jié)構(gòu),經(jīng)驗分享,其他

?????????執(zhí)行次數(shù)符合2^N增長，但是執(zhí)行到最后也并不能完全算的上是2^N，最后在右下角部分會率先遞歸到Fib(0)，所以右下角會缺失一部分。但時間復(fù)雜度本身就是一個估算的結(jié)果，所以它的時間復(fù)雜度仍為O(2^N)

3.空間復(fù)雜度

定義：

?空間復(fù)雜度是算法在運行過程中臨時占用存儲空間大小的量度。

????????空間復(fù)雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復(fù)雜度算的是變量的個數(shù)?？臻g復(fù)雜度計算規(guī)則基本跟時間復(fù)雜度類似，也使用大O漸進表示法。注意：函數(shù)運行時所需要的?？臻g(存儲參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過函數(shù)在運行時候顯式申請的額外空間來確定。

?例1：

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)，為什么？空間復(fù)雜度是算法在運行過程中臨時占用存儲空間大小的量度，主要通過函數(shù)在運行時候顯式申請的額外空間來確定。冒泡排序在解決排序問題的過程中并沒有向內(nèi)存申請額外的空間。所以空間復(fù)雜度為 O(1)。

例2：

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

這個程序的空間復(fù)雜度是多少？

? ? ? ? 答案是O(N)。這個程序使用數(shù)組來實現(xiàn)斐波那契數(shù)列，在程序中額外申請了n+1個存儲數(shù)據(jù)的空間，動態(tài)開辟了N個空間，空間復(fù)雜度為 O(N)。

?例3：

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

這個遞歸的空間復(fù)雜度是多少？

????????答案是O(N)，遞歸在調(diào)用自身的同時會保留當前的棧幀，然后繼續(xù)開辟新的函數(shù)棧幀，這里遞歸合計開辟了N個棧幀。每個棧幀開辟常數(shù)個空間，所以空間復(fù)雜度是O(N)，可能還會有人問，函數(shù)棧幀不是不算嗎？這里注意，空間復(fù)雜度的定義是算法在運行過程中臨時占用存儲空間大小的量度，主要通過函數(shù)在運行時候顯式申請的額外空間來確定。只有第一個遞歸函數(shù)不算，其他開辟的函數(shù)棧幀都屬于額外開辟的空間。

? ? ? ? 我們可以總結(jié)一下遞歸與普通函數(shù)的區(qū)別：普通函數(shù)只需計算當前函數(shù)中的時間和空間消耗，遞歸函數(shù)需要計算調(diào)用的所有函數(shù)消耗的時間和空間。

?例4：

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

?為了大家能夠更深刻的理解，這里我們再來看看上述的這個雙路遞歸，它的空間復(fù)雜度是多少？

????????答案是O(N)，為什么呢？注意這里計算的是空間復(fù)雜度，空間和時間的區(qū)別在哪？空間可以復(fù)用，而時間不可以。當一個遞歸率先到達Fib(0)時，就會返回上一層遞歸，而返回的同時也會將空間還給操作系統(tǒng)，這個雙路遞歸最多會在棧區(qū)向下創(chuàng)建N+1個函數(shù)棧幀。所以它的空間復(fù)雜度是O(N)?？偨Y(jié)一下：我們常見的程序，空間復(fù)雜度一般都是O(N)或者O(1)，如果空間復(fù)雜度過高會造成程序消耗內(nèi)存過高，程序會崩潰。

4.常見復(fù)雜度對比

一般常見的復(fù)雜度如下：

從頭開始：數(shù)據(jù)結(jié)構(gòu)和算法入門（時間復(fù)雜度、空間復(fù)雜度）,算法,數(shù)據(jù)結(jié)構(gòu),經(jīng)驗分享,其他

?增長曲線如下：

從頭開始：數(shù)據(jù)結(jié)構(gòu)和算法入門（時間復(fù)雜度、空間復(fù)雜度）,算法,數(shù)據(jù)結(jié)構(gòu),經(jīng)驗分享,其他

總結(jié)

? ? ? ? 日常生活中我們會遇到很多問題需要算法解決，在選擇算法時，我們需要綜合考慮時間復(fù)雜度和空間復(fù)雜度，找到一個合適的平衡點，以滿足問題的要求和資源的限制。通過分析算法復(fù)雜度，我們可以評估算法的效率和可行性，并選擇最優(yōu)的算法來解決問題。好的本期內(nèi)容到此結(jié)束。最后，感謝閱讀！

到了這里，關(guān)于從頭開始：數(shù)據(jù)結(jié)構(gòu)和算法入門（時間復(fù)雜度、空間復(fù)雜度）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！