C語言數據結構的時間復雜度和空間復雜度實例分析

這篇文章主要講解了“C語言數據結構的時間復雜度和空間復雜度實例分析”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“C語言數據結構的時間復雜度和空間復雜度實例分析”吧！

一、數據結構前言        

1.什么是數據結構:        

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

2.什么是算法？        

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

通俗來說:二分查找，冒泡排序等等都為算法   

3.如何學好算法和數據結構       

1.多寫代碼(寫到吐)

2.勤于思考多畫圖

注:學習數據結構為軟件開發打下深厚功底，提升代碼能力    

二、算法的時間復雜度和空間復雜度

1.算法效率

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

比如對于以下斐波那契數列：

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

 1.2算法的復雜度

算法在編寫成可執行程序后，運行時需要耗費時間資源和空間(內存)資源 。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。時間復雜度主要衡量一個算法的運行快慢，而空間復雜度主要衡量一個算法運行所需要的額外空間。在計算機發展的期，計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經過計算機行業的迅速發展,計算機的存儲容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個算法的空間復雜度。

2.時間復雜度

2.1 時間復雜度的概念

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

 注:算法中的基本操作的執行次數，為算法的時間復雜度。

求其時間復雜度：

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

操作次數:

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

2.2大O的漸進表示法

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

1、用常數1取代運行時間中的所有加法常數。
2、在修改后的運行次數函數中，只保留最高階項。
3、如果最高階項存在且不是1，則去除與這個項目相乘的常數。得到的結果就是大 O 階。

 使用大O的漸進表示法以后，Func1的時間復雜度為： N^2

 N = 10 F(N) = 100

N = 100 F(N) = 10000

N = 1000 F(N) = 1000000

 實例1.計算Func2的時間復雜度？

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

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

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

時間復雜度并不代表1次，而是常數次

實例4：計算strchr的時間復雜度

//計算strchr的時間復雜度
const char * strchr ( const char * str, int character );
{
    while(*str)
    {
        if(*str == character)
        {
            return str;
        }
    }
}

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

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

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

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

 3.空間復雜度

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

4. 常見復雜度對比

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

感謝各位的閱讀，以上就是“C語言數據結構的時間復雜度和空間復雜度實例分析”的內容了，經過本文的學習后，相信大家對C語言數據結構的時間復雜度和空間復雜度實例分析這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！