前言

新的學習階段又開始了,在更新完C語言后,博主將開始更新資料結構的知識了,說到資料結構想必大家都是知道其重要性吧.

嗯,廢話不多說,那我們現在就開始談談資料結構吧~

演算法效率

什么是演算法效率? 即判斷一個程式的相對好與壞的方法.演算法效率的測評主要有兩種:

• 第一種: 時間復雜度(又稱時間效率)
• 第二種: 空間復雜度(又稱空間效率)

而由于現在科技的飛速發展,計算機的存盤容量已經極大提高,空間復雜度并不是重點了,我們今天需要著重講解的就是時間復雜度

時間復雜度

!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!敲黑板!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !! !!! !!!

重要的事情一定要多說幾遍,時間復雜度測的

!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!不是時間!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!!

!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!不是時間!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!!

!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!不是時間!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!!

一個程式的執行時間完全會受到很多因素的影響,比如同樣的程式,在不同的機器,執行的時間卻不一定相同,所以說如果我們要用 時間的長短來評價一個程式的好壞這明顯是不科學的,因此才提示時間復雜度的概念 : 演算法中的基本操作執行次數,而他的表示方法則是大O漸進表示法,即O(m) ,m是關于次數的運算式

樣例1

請問函式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) = N2 + 2N + 10;

所以用大O漸進表示法就是O(N2 + 2N + 10),對嗎???,先不回答,我們先看看下面:

我們發現,隨著N的逐漸增大,F(N)的值也逐漸增大,但是卻也與N2的值非常接近,因此我們便可以不看尾數,即我們再用大O漸進表示法時候是不需要精確計算運行次數,而只是求個大概.

1. **下面是總結的大O表示原則:**

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

所以Func1的時間復雜度是 O(N2),同時提醒一下哦,時間復雜度計算的是在最壞情況下的哦

樣例2

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

經過分析可以得知,Func2的基本執行次數是:

? F(N) = 2N + 10;

根據大O表示法原則第一條F(N)變成: F(n) = 2N + 1;

根據大O表示法原則第二條F(N)變成: F(n) = 2N;

根據大O表示法原則第三條F(N)變成: F(n) = N;

所以最終時間復雜度是 : O(N)

樣例3

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

經過分析可以得知,Func3的基本執行次數是:

?

? F(N) = M + N

根據大O漸進表示法原則,可以知道 時間復雜度為: O( M + N)

樣例4

void Func4(int N)
{
    int count = 0;
    for (int k = 0; k < 100; ++ k)
    {
    	++count;
    }
    printf("%d\n", count);
}

經過分析可以得知,Func4的基本執行次數是:

?

? F(N) = 100

根據大O漸進表示法原則,可以知道 時間復雜度為: O(1)

樣例5

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

經過分析可以得知,BubbleSort的基本執行次數是:

?

? F(N) = n-1 + n-2 + n-3 + n-4 + … + 3 + 2 + 1;

可以知道那是一個等引數列求和,所以F(N) = n(n-1) / 2 = (1/2)N2 - (1/2)N*

按照大O表示法可以知道 時間復雜度為 O(N2)

樣例6

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

請看下面隨著查找次數與陣列長度關系:

由此我們可以知道一個關系: 2^x = N,所以 x = ㏒?(N), 即 F(N) = ㏒?(N)

所以大O漸進表示法 時間復雜度為 O(㏒?(N))

遞回的時間復雜度求解

遞回復雜度的計算公式為: 遞回次數 * 每次遞回里面的基本操作次數

樣例1

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

遞回次數: N

每次遞回基本操作次數: 1

**所以F(N) = N*1; **

大O的漸進表示法 時間復雜度為:O(N)

樣例2

long long Fibonacci(size_t N)
{
	return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}

遞回次數:

所以F(N) = 2^0 + 2^1 + 2^2 + … 2^(n-2)

*這是等比數列求和,所以F(N) = (1-2(n-2)) / (1-2) = 2^(n-2) - 1 = (1/4)2^n - 1

所以大O表示法的 時間復雜度是 O(2^N)****

有人可能會說,這個是不準確的,的確,因為實際上這個次數是小于2^(n-2) - 1的,為什么呢,請看圖:

即在中途后,次數就開始下降了,原因是有F(3)以下的數字先達到,就不再需要往下遞回了.

但是即使這樣,我們想一想按照這樣真實的計算,最高次項是多少?? 其實還是2^N,所以時間復雜度仍然為O(2^N)

空間復雜度

!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!!敲重點!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!!

!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! 空間復雜度 !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!!

計算的不是記憶體大小,而是程式每次執行,說臨時開辟的變數數量

并且時間復雜度是累積的,但是空間復雜度不累計,并且空間復雜度的表示也是大O表示

樣例1

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

通過觀察可以看見,程式開辟的變數數量只有3個,即常數個,所以 空間復雜度為 O(1)

樣例2

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+1個空間,所以空間復雜度為O(N)

樣例3

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

由于是遞回,遞回的空間復雜度計算類似. 等于遞回開辟的堆疊空間*每次遞回開辟的變數數量

此題每次遞回沒有開辟變數,所以只計算遞回次數,可知道連續遞回了N次,所以O(N)

樣例4

long long Fibonacci(size_t N)
{
	return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}

還記得我們說過的,空間復雜度不累計嗎???

這個題做多連續遞回多少次? 答案n-1,

因為要想知道F(N)必先知道F(N-1),要想知道F(N-1)必先知道F(N-2)…依次往下.

每次遞回時候并沒有開辟變數數量,所以空間復雜度為O(n)