今天是2020年4月29日，從今天開始學習資料結構，寫博客的目的一是為了鞏固與分享今天課堂上所學習的知識，二是可以督促自己希望自己可以堅持下去，如果哪個地方我說錯了，評論請輕點噴（博主是小白，第一次接觸資料結構，希望可以和大家一起努力共同進步）

正文開始

資料結構

1、什么是資料結構？

2、什么是演算法？

3、衡量一個演算法是否良好的因素？

4、時間復雜度

4.1時間復雜度的概念

4.2大O的漸進表示法

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

5、空間復雜度

5.1空間復雜度是什么？

5.2實體

資料結構

1、什么是資料結構？

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

2、什么是演算法？

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

3、衡量一個演算法是否良好的因素？

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

4、時間復雜度

4.1時間復雜度的概念

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

4.2大O的漸進表示法

// 請計算一下Func1基本操作執行了多少次？
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的漸進表示法，
大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)

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

結果： $O(N)$

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

結果： $O(N+M)$

實體3：

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

結果： $O(1)$

實體4：

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

strchr函式功能為在一個串中查找給定字符的第一個匹配之處，函式原型為：char *strchr(const char *str, int c)，即在引數 str 所指向的字串中搜索第一次出現字符 c（一個無符號字符）的位置，strchr函式包含在C 標準庫 <string.h>中，

若給定字符為str中第一個字符，則最好的結果執行1次，若為最后一個，則最壞N次，時間復雜度一般看最壞,則結果為 $O(N)$ .

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

外層回圈控制趟數，內層回圈進行比較，將相鄰兩元素不斷比較交換，

其基本操作執行最好N次，最壞執行了(N*(N+1)/2次，通過推導大O階方法+時間復雜度一般看最壞，時間復雜度為 O(N^2)

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

盡量不要使用：

int mid = （begin+end）/ 2;

而使用這句，不是說上面有錯，而是在begin和end都非常大的時候容易發生資料溢位，

  int mid = begin + ((end-begin)>>1);

這句相當于回圈右移，原因如圖所示：

可以通過根據二分法畫圖來計算其時間復雜度，如下：

即基本操作執行最好1次，最壞O(logN)次，時間復雜度為 O(logN) ps：logN在演算法分析中表示是底數為2，對數為N，有些地方會寫成lgN，

實體7

// 計算階乘遞回Factorial的時間復雜度？
long long Factorial(size_t N)
{
    return N < 2 ? N : Factorial(N-1)*N;
}

這塊階乘表示的不是很嚴謹，當看不出來的時候，畫圖：

遞回函式時間復雜度：單次遞回次數*總的遞回次數

（常數）（N+1）

所以時間復雜度為：O(N)

實體8：

// 計算斐波那契遞回Fibonacci的時間復雜度？
long long Fibonacci(size_t N)
{
    return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}

示意圖如下：

通過計算分析發現基本操作遞回了2^N次，時間復雜度為O(2^N)，（建議畫圖遞回堆疊幀的二叉樹講解），不懂就畫圖---真理

那么問題來了，你能把斐波那契數列的時間復雜度優化到O(N)嗎？

unsigned long long Fib1(int n)
{
	long long first = 1;
	long long second = 1;
	long long ret = 1;
	for (int i = 3; i <= n; ++i)
	{
	    ret = first + second;
		first = second;
		second = ret;
	}
	return ret;
}

5、空間復雜度

5.1空間復雜度是什么？

空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的量度，空間復雜度不是程式占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數，空間復雜度計算規則基本跟時間復雜度類似，也使用大O漸進表示法，

空間復雜度：函式中所需要空間的個數關于N的數學運算式

5.2實體

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

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

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

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282112.html

標籤：其他

上一篇：JavaScript學習（六十四）—關于JS的浮點數計算精度問題解決方案

下一篇：獨立按鍵控制直流電機轉動

資料結構 一、時間復雜度與空間復雜度

資料結構

1、什么是資料結構？

2、什么是演算法？

3、衡量一個演算法是否良好的因素？

4、時間復雜度

4.1時間復雜度的概念

4.2大O的漸進表示法

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

5、空間復雜度

5.1空間復雜度是什么？

5.2實體

資料結構一、時間復雜度與空間復雜度