C語言中算法的時間復雜度和空間復雜度是什么

這篇文章給大家分享的是有關C語言中算法的時間復雜度和空間復雜度是什么的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

1.前言

1.1 什么是數據結構？

數據結構(Data Structure)是計算機存儲、組織數據的方式，指相互之間存在一種或多種特定關系的數據元素的集合。

1.2 什么是算法？

算法(Algorithm):就是定義良好的計算過程，他取一個或一組的值為輸入，并產生出一個或一組值作為輸出。簡單來說算法就是一系列的計算步驟，用來將輸入數據轉化成輸出結果。

2.算法效率

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

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

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

斐波那契數列的遞歸實現方式非常簡潔，但簡潔一定好嗎？那該如何衡量其好與壞呢？

2.2 算法的復雜度

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

時間復雜度主要衡量一個算法的運行快慢，而空間復雜度主要衡量一個算法運行所需要的額外空間。在計算機發展的早期，計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經過計算機行業的迅速發展，計 算機的存儲容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個算法的空間復雜度

2.3 復雜度在校招中的考察

3.時間復雜度

3.1 時間復雜度的概念

時間復雜度的定義：在計算機科學中，算法的時間復雜度是一個函數，它定量描述了該算法的運行時間。一個算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復雜度這個分析方式。

一個算法所花費的時間與其中語句的執行次數成正比例，算法中的基本操作的執行次數，為算法的時間復雜度即：找到某條基本語句與問題規模N之間的數學表達式，就是算出了該算法的時間復雜度

// 請計算一下Func1中++count語句總共執行了多少次？
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 執行的基本操作次數 ：F(N) = N^2+2*N+10

(‘^’在此章節表示為數乘)

• N = 10 F(N) = 130

• N = 100 F(N) = 10210

• N = 1000 F(N) = 1002010

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

3.2 大O的漸進表示法

大O符號（Big O notation）：是用于描述函數漸進行為的數學符號。

推導大O階方法：

1、用常數1取代運行時間中的所有加法常數。

2、在修改后的運行次數函數中，只保留最高階項。

3、如果最高階項存在且不是1，則去除與這個項目相乘的常數。得到的結果就是大O階。使用大O的漸進表示法以后，Func1的時間復雜度為：O(N^2)

• N = 10 F(N) = 100

• N = 100 F(N) = 10000

• N = 1000 F(N) = 1000000

通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數。

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

最壞情況：任意輸入規模的最大運行次數(上界)

平均情況：任意輸入規模的期望運行次數

最好情況：任意輸入規模的最小運行次數(下界)

例如：在一個長度為N數組中搜索一個數據x

最好情況：1次找到

最壞情況：N次找到

平均情況：N/2次找到

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

3.3 常見時間復雜度計算舉例

實例1

// 計算Func2的時間復雜度？
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);
}

實例 2

// 計算Func3的時間復雜度？
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);
}

實例 3

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

實例 4

// 計算strchr的時間復雜度？
const char * strchr ( const char * str, int character );

實例 5

// 計算BubbleSort的時間復雜度？
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;
    }
}

實例 6

// 計算BinarySearch的時間復雜度？
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;
    }
    return -1;
}

實例 7

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

實例 8

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

實例答案及分析：

實例1基本操作執行了2N+10次，通過推導大O階方法知道，時間復雜度為 O(N)

實例2基本操作執行了M+N次，有兩個未知數M和N，時間復雜度為 O(N+M)

實例3基本操作執行了10次，通過推導大O階方法，時間復雜度為 O(1)

實例4基本操作執行最好1次，最壞N次，時間復雜度一般看最壞，時間復雜度為 O(N)

實例5基本操作執行最好N次，最壞執行了(N*(N+1)/2)次（N-1 + N-2 + N-3…+2+1），通過推導大O階方法+時間復雜度一般看最壞，時間復雜度為 O(N^2)。

實例6基本操作執行最好1次（第一次就找到了），最壞O(logN)次(全找了一遍但沒找到的情況），時間復雜度為 O(logN) ps：logN在算法分析中表示是底數為2，對數為N。有些地方會寫成lgN。（建議通過折紙查找的方式講解logN是怎么計算出來的）（假設找了x次才找完，則共有2^x個數據。反過來講就是N個數據最多要找logN（底數為2）次）

實例7通過計算分析發現基本操作遞歸了N次，時間復雜度為O(N)。

實例8通過計算分析發現基本操作遞歸了2^N 次，時間復雜度為O(2N)。（1+2+4+8……+2(n-1) 再減一些次數（忽略不計））（建議畫圖遞歸棧幀的二叉樹)

總結：我們想要分析算法的時間復雜度，一定要去看思想，，不能只去看程序是幾層循環。 遞歸算法時間復雜度的計算：

1.每次函數調用是O(1)，那么就看遞歸次數

2.每次函數調用不是O(1),就把每次的調用次數相加。

4.空間復雜度

空間復雜度也是一個數學表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度 。

空間復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數。空間復雜度計算規則基本跟實踐復雜度類似，也使用大O漸進表示法。

注意：函數運行時所需要的棧空間(存儲參數、局部變量、一些寄存器信息等)在編譯期間已經確定好了，因此空間復雜度主要通過函數在運行時候顯式申請的額外空間來確定。

實例 1

// 計算BubbleSort的空間復雜度？
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;
    }
}

實例 2

// 計算Fibonacci的空間復雜度？
// 返回斐波那契數列的前n項
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;
}

實例 3

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

實例4

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

實例答案及分析：

實例1使用了常數個額外空間，所以空間復雜度為 O(1)

實例2動態開辟了N個空間，空間復雜度為 O(N)

實例3遞歸調用了N次，開辟了N個棧幀，每個棧幀使用了常數個空間。空間復雜度為O(N) 4.先說答案空間復雜度為O(N) ，這是因為它與棧幀的開辟與銷毀有關。棧幀銷毀后再開辟還是用的同一塊空間，它遞歸2^N次，開辟N個空間算出數值后銷毀空間，然后再開辟，總共用了N塊空間

總結： 時間一去不復返，是累積的 空間回收以后可以重復利用

5. 常見復雜度對比

一般算法常見的復雜度如下：

感謝各位的閱讀！關于“C語言中算法的時間復雜度和空間復雜度是什么”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！