時間復雜度的計算

1.時間復雜度

時間復雜度的定義：在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，
一個演算法所花費的時間與其中陳述句的執行次數成正比例，所以演算法中的基本操作的執行次數，為演算法的時間復雜度，

大O用來表示程式執行次數的

大O的漸進法表示

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

void Func1(int N)
 {
 int count = 0;//執行次數為1
 for (int i = 0; i < N ; ++ i) 
 {
  for (int j = 0; j < N ; ++ j)
   {
   ++count;//1.count執行次數為N^2
   }
 }
 for (int k = 0; k < 2 * N ; ++ k) 
 {
   ++count;//2.count執行次數為2*N
 }
  int M = 10;
while (M--)
 {
 ++count;//count執行次數為10次
 }
printf("%d\n", count);//執行次數為1
}

所以此函式執行次數的關系式為：

N總=1+n^2+2n+10+1=2n+12+n*n;

當n趨于無窮大時n^2是2*n和12的高階無窮小，所以N總的大小不用考慮這兩項，此外高階無窮小前的系數在n->無窮的時候不考慮，

保留最高階項，忽略最高階前的系數

所以此函式的時間復雜度為O(n^2)

常見的時間復雜度有：常數階O(1),對數階O(log2n),線性階O(n), 線性對數階O(nlog2n),平方階O(n2)，立方階O(n3) k次方階,指數階O(2^n)，

注意O(1)表示常數次，這個常數次可以很大

如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條陳述句，其執行時間也不過是一個較大的常數，此類演算法的時間復雜度是O(1)，
eg:

int main()
{
	int i = 0;
	for (i = 0; i < 1000000000; i++)
	{
		;
	}
	return 0;
}

回圈次數雖然多，但這只是很大的常數，所以時間復雜度仍為O（1）

最好、平均和最壞情況

例如：查找演算法

最好情況：查找一次就找到了，

最壞情況：查找了N次查找到了，

平均情況：（1+N）/2

在實際中一般情況關注的是演算法的最壞運行情況，所以陣列中搜索資料時間復雜度為O(N)

具體函式分析

一：

void Func2(int N) {
int count = 0;//執行1次
for (int k = 0; k < 2 * N ; ++ k) {
 ++count; }//執行2*N
int M = 10;//執行1次
while (M--) {
 ++count; }//執行10次
printf("%d\n", count);//執行一次
}

所以執行次數函式為

N總=2*n+12;

大O法只保留最高階，且忽略最高階前的系數
所以Func2（）的時間復雜度為O(N)

二：

void Func3(int N, int M) {
int count = 0;//執行1次
for (int k = 0; k < M; ++ k) {
 ++count; }//執行M次
for (int k = 0; k < N ; ++ k) {
 ++count; }//執行N次
printf("%d\n", count);//執行1次
}

所以執行次數的函式為：
N總=m+n+2;
注意：在這里不能確定m,n，有兩個未知數會影響執行次數，且這兩個未知數的階數相同，所以不能輕易省略，

所以大O表示Func3（）函式的時間復雜度為O(M+N)

三：

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

所以執行次數的函式為：
N總=11
演算法的執行時間不隨著問題規模n的增加而增長

所以大O表示Func4（）函式的時間復雜度為O（1）

四：

char* strchr(char *s, char c)
{
    while(*s != '\0' && *s != c)
    {
        ++s;//執行N次，與傳入函式的字串有關
    }
    return *s==c ? s : NULL;
}

所以函式strchar（）執行次數的運算式為:
最好為1次，最壞為N次
大O法表示為其最壞的情況.

所以strchr函式的時間復雜度為O（N）

五：

//冒泡排序法
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的陣列首元素地址，以及陣列長度

exchange的作用為記錄陣列是否交換，

1.如果exchange的值在經歷了第一次回圈后還是0，表明該陣列已經有序，不需要交換，直接回傳，只是經過了一次查找陣列

所以可以知道演算法最好情況用大O法表示為O(N)；

2.在經歷了第一次回圈N-1次后end減少，下一次回圈次數變為N-2次，
所以所以函式BubbleSort（）執行次數的運算式為:

(N-1)+(N-2)+(N-3)…+1=(1+N-1)*(N-1)/2=N(N-1)/2

大O法表示為其最壞的情況.

大O法只保留最高階，且忽略最高階前的系數O(N^2)

六：

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份，查找二次,N被分成4份，
設查找的f(x)次,此時N被分成2^f(x)份，
2^f(x)=N,解得f(x)=logN，這個就是它的執行次數，

所以用大O法表示為O(logN)

七：

long long Factorial(size_t N) {
return N < 2 ? N : Factorial(N-1)*N; }
//這個代碼是遞回求階乘

遞回的時間復雜度=遞回次數*每次遞回程序中函式的執行次數

階乘遞回的次數是從N到1，共有N次，每一次遞回程序中函式執行次數是1次（一句三目運算子）

所以Factorial()的時間復雜度為O(N*1)=O(N);

注意：
如果還是遞回N次，但每一次遞回都有一個
for(int i=0;i<N;i++){}；這時每次遞回程序中函式執行次數為N次
時間復雜度變為O(N*N)=O(N^2)

八：

long long Fibonacci(size_t N) {
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);斐波那契數列
}

為了方便舉例子，這里先從N=4的時候說起

每一次函式的執行次數為1

所以大O表示O(2^N*1)