@
目錄
- 前言
- 算法效率
- 時間複雜度
- 樣例1
- 樣例2
- 樣例3
- 樣例4
- 樣例5
- 樣例6
- 遞歸的時間複雜度求解
- 空間複雜度
新的學習階段又開始了,在更新完C語言後,部落客将開始更新資料結構的知識了,說到資料結構想必大家都是知道其重要性吧.
嗯,廢話不多說,那我們現在就開始談談資料結構吧~
什麼是算法效率? 即
判斷一個程式的相對好與壞的方法
.算法效率的測評主要有兩種:
- 第一種: 時間複雜度(又稱時間效率)
- 第二種: 空間複雜度(又稱空間效率)
而由于現在科技的飛速發展,計算機的存儲容量已經極大提高,
空間複雜度
并不是重點了,我們今天需要着重講解的就是
時間複雜度
!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!敲黑闆!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !! !!! !!!!
重要的事情一定要多說幾遍,時間複雜度測的
!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!不是時間!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!!
一個程式的執行時間完全會受到很多因素的影響,比如同樣的程式,在不同的機器,執行的時間卻不一定相同,是以說如果我們要用 時間的長短來評價一個程式的好壞這明顯是不科學的,是以才提示時間複雜度的概念 :
算法中的基本操作執行次數
,而他的表示方法則是大O漸進表示法,即O(m) ,m是關于次數的表達式
請問函數
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² + 2N + 10;
是以用大O漸進表示法就是O(N² + 2N + 10),對嗎???,先不回答,我們先看看下面:
| N | F(N) | N² |
|---|---|---|
| 1 | 13 | |
| 10 | 130 | 100 |
| 10210 | 10000 | |
| 1000 | 1002010 | 1000000 |
| 100020010 | 100000000 |
我們發現,随着N的逐漸增大,F(N)的值也逐漸增大,但是卻也與N²的值非常接近,是以我們便可以不看尾數,即我們再用大O漸進表示法時候是不需要精确計算運作次數,而隻是求個大概.
-
**下面是總結的大O表示原則:**
-
**用常數1取代運作時間中的所有加法常數。**
-
**在修改後的運作次數函數中，隻保留最高階項。**
-
**如果最高階項存在且不是1，則去除與這個項目相乘的常數。得到的結果就是大O階**
-
是以
Func1
的時間複雜度是
O(N²)
,同時提醒一下哦,時間複雜度計算的是
在最壞情況下的哦
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)
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)
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}
經過分析可以得知,Func4的基本執行次數是:
F(N) = 100
時間複雜度為: 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;
}
}
經過分析可以得知,BubbleSort的基本執行次數是:
F(N) = n-1 + n-2 + n-3 + n-4 + ... + 3 + 2 + 1;
可以知道那是一個等差數列求和,是以F(N) = n*(n-1) / 2 = (1/2)N² - (1/2)N
按照大O表示法可以知道
時間複雜度為 O(N²)
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;
}
請看下面随着查找次數與數組長度關系:
| 查找次數 | 數組長度 |
|---|---|
| N/2 | |
| 2 | N/2/2 |
| 3 | N/2/2/2 |
| ... | |
| x-2 | |
| x-1 | |
| x |
由此我們可以知道一個關系: 2^x = N,是以 x = ㏒₂(N), 即 F(N) = ㏒₂(N)
是以大O漸進表示法
時間複雜度為 O(㏒₂(N))
遞歸複雜度的計算公式為:
遞歸次數
*
每次遞歸裡面的基本操作次數
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}
遞歸次數: N
每次遞歸基本操作次數: 1
**是以F(N) = N*1; **
大O的漸進表示法
時間複雜度為:O(N)
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表示
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)
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)
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}
由于是遞歸,遞歸的空間複雜度計算類似. 等于
遞歸開辟的棧空間
每次遞歸開辟的變量數量
此題每次遞歸沒有開辟變量,是以隻計算
遞歸次數
,可知道連續遞歸了N次,是以
O(N
)
long long Fibonacci(size_t N)
{
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}
還記得我們說過的,空間複雜度不累計嗎????????????