一、數(shù)據(jù)結(jié)構(gòu)前言        

1.什么是數(shù)據(jù)結(jié)構(gòu):        

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

2.什么是算法？        

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

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

3.如何學(xué)好算法和數(shù)據(jù)結(jié)構(gòu)       

1.多寫代碼(寫到吐)

2.勤于思考多畫圖

注:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)為軟件開發(fā)打下深厚功底，提升代碼能力    

二、算法的時(shí)間復(fù)雜度和空間復(fù)雜度

1.算法效率

1.1如何衡量一個(gè)算法的好壞

比如對(duì)于以下斐波那契數(shù)列：

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

 1.2算法的復(fù)雜度

算法在編寫成可執(zhí)行程序后，運(yùn)行時(shí)需要耗費(fèi)時(shí)間資源和空間(內(nèi)存)資源 。因此衡量一個(gè)算法的好壞，一般是從時(shí)間和空間兩個(gè)維度來衡量的，即時(shí)間復(fù)雜度和空間復(fù)雜度。時(shí)間復(fù)雜度主要衡量一個(gè)算法的運(yùn)行快慢，而空間復(fù)雜度主要衡量一個(gè)算法運(yùn)行所需要的額外空間。在計(jì)算機(jī)發(fā)展的期，計(jì)算機(jī)的存儲(chǔ)容量很小。所以對(duì)空間復(fù)雜度很是在乎。但是經(jīng)過計(jì)算機(jī)行業(yè)的迅速發(fā)展,計(jì)算機(jī)的存儲(chǔ)容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個(gè)算法的空間復(fù)雜度。

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

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

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

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

求其時(shí)間復(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);
}

操作次數(shù):

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

2.2大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 階。

 使用大O的漸進(jìn)表示法以后，F(xiàn)unc1的時(shí)間復(fù)雜度為： N^2

 N = 10 F(N) = 100

N = 100 F(N) = 10000

N = 1000 F(N) = 1000000

 實(shí)例1.計(jì)算Func2的時(shí)間復(fù)雜度？

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

實(shí)例2.計(jì)算Func3的時(shí)間復(fù)雜度？

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

實(shí)例3：計(jì)算Func4的時(shí)間復(fù)雜度？

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

時(shí)間復(fù)雜度并不代表1次，而是常數(shù)次

實(shí)例4：計(jì)算strchr的時(shí)間復(fù)雜度

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

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

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

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

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

 3.空間復(fù)雜度

空間復(fù)雜度也是一個(gè)數(shù)學(xué)表達(dá)式，是對(duì)一個(gè)算法在運(yùn)行過程中 臨時(shí)占用存儲(chǔ)空間大小的量度 。
空間復(fù)雜度不是程序占用了多少 bytes 的空間，因?yàn)檫@個(gè)也沒太大意義，所以空間復(fù)雜度算的是變量的個(gè)數(shù)。
空間復(fù)雜度計(jì)算規(guī)則基本跟實(shí)踐復(fù)雜度類似，也使用 大 O 漸進(jìn)表示法 。
注意：函數(shù)運(yùn)行時(shí)所需要的?？臻g(存儲(chǔ)參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過函數(shù)在運(yùn)行時(shí)候顯式申請(qǐng)的額外空間來確定。

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

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

到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)的時(shí)間復(fù)雜度和空間復(fù)雜度的文章就介紹到這了,更多相關(guān)C語言時(shí)間與空間復(fù)雜度內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論