前言：

• 博主新開了一個專欄《資料結構與演算法》，望各位大佬，多多支持，非常感謝！

• 博主目前處于資料結構的入門階段，博文有什么錯誤，望各位大佬 不吝賜教，非常感謝！

• 就像C生萬物一樣，資料結構與演算法之間的是形影不離的，談到數位元組構必然要談演算法的，

演算法高效性的2個主要指標：時間復雜度，空間復雜度

時間復雜度（執行演算法的時間成本）

序章：

• 由于受運行環境和輸入規則的影響，代碼的絕對執行時間是不可預知的，但是我們卻可以預估代碼的基本執行操作執行次數T(N)，來預估代碼執行時間，但是對與不同演算法，以T(N1)=0.5N² +0.5N，T(N2)=100N為例，我們當如何比較呢？

• 為了解決時間分析問題，有了漸進時間復雜度

官方定義：

若存在函式f(N),使得當N趨于無窮大時，T(N)/f(N)的極限值是不為0的常數，則稱f(N)是T(N)的同量級函式，記作：T(N)=0(f(N)), 0為演算法的漸進時間復雜度，簡稱時間復雜度

因為漸進時間復雜度用大寫0來表示，所以也稱為大0 漸進法

• 時間復雜度表示法：大0表示法

規則：

• 如果運行時間是常數量級，則用常數1表示

• 只保留最影響執行次數的那一項

• 如果那一項存在，則省去哪一項前面的系數，因為當N很大時，系數已無關緊要，

普通函式的時間復雜度

EXP1:

/ 請計算一下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);
}

• F(N)=N² + 2*N +10

F(N)
F(10)	130
F(100)	10210
F(1000)	1002010
…

• 當N趨于無窮大時，對于F(N)可以說只有N² 在影響結果，因此這也就是大0漸進的原因

• 但是對與一個演算法，以二分查找為例，我們必須考慮不同的情況

最壞情況	任意輸入規模的最大運行次數(上界），二分查找要找到最后
平均情況	任意輸入規模的期望運行次數，二分查找要找到中間
最好情況	任意輸入規模的最小運行次數(下界)，二分查找第一次就找到

• 在實際中一般情況關注的是演算法的最壞運行情況，就像等人一樣，要做好等待時間超過心里預期的情況，

• 因此fun1的時間復雜度是：0(N² )

EXP2:

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

• 時間復雜度：0(M+N);

M于N互不相關，因此獨立計算執行次數

EXP3:

// 計算BubbleSort（冒泡法）的時間復雜度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t i = 0; i <n-1; i++)
{
int exchange = 0;
for (size_t j = 0; j < end-1-i; j++)
{
if (a[j] > a[j+1])
{
Swap(&a[j], &a[j+1]);
exchange = 1;
}
}
if (exchange == 0)//如果沒發生交換，說明陣列已經是按從小到大排好序了
break;
}

• 時間復雜度：0(N²)

EXP4:

// 計算BinarySearch(二分查找)的時間復雜度？
//默認陣列從小到大排好序了
int BinarySearch(int* a, int n, int x)
{
assert(a);
int left= 0;
int right= n-1;
while (left <= right)
{
int mid =(left+right)/2;
if (a[mid] < x)
{
    left = mid+1;
}
else if (a[mid] > x)
{
    right= mid-1;
}  
  else
  { 
      return mid;
  }
}
return -1;
}

• 時間復雜度：0(log2ⁿ)

遞回函式的時間復雜度

遞回函式的時間復雜度，我們看的是其遞回次數也就是深度，

EXP1:

long long Factorial(size_t N)//階層
{
return N < 2 ? N : Factorial(N-1)*N;
}

• 遞回深度為：N，因此時間復雜度：0（N）

EXP2：

long long Fibonacci(int N)
{

return N<2 ? N:Fiboncci(N-1)+Fiboncci(N-2)

}

時間復雜度：0(2^N)

空間復雜度（執行演算法的空間成本）：

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

普通函式的空間復雜度：

EXP1:

void BubbleSort(int* a, int n)
{
assert(a);
for (size_t i = 0; i <n-1; i++)
{
int exchange = 0;
for (size_t j = 0; j < end-1-i; j++)
{
if (a[j] > a[j+1])
{
Swap(&a[j], &a[j+1]);
exchange = 1;
}
}
if (exchange == 0)//如果沒發生交換，說明陣列已經是按從小到大排好序了
break;
}

• 空間復雜度：因為臨時變數（形參也算）是常數個，因此空間復雜度：0（1）

EXP2：

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

空間復雜度：因為臨時開辟了N個空間因此空間復雜度是0（N）

遞回函式的空間復雜度：

EXP1:

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

• 因為每次遞回了N次，因此函式堆疊幀了N次，但是每次都是常數個變數，因此空間復雜度為：0（N）

EXP2：

long long Fibonacci(int N)
{

return N<2 ? N:Fiboncci(N-1)+Fiboncci(N-2)

}

• 遞回是樹形，因此空間復雜度是0（N）

總結

• 博主目前處于《資料結構》的入門階段，因此博文有什么錯誤，請各位大佬指出，非常感謝！