1.時間復雜度的定義
在計算機科學中，算法的時間復雜度是一個函數，它定量描述了算法的運行時間。一個算法所花費的時間與其中語句的執行次數成正比列，算法中的基本操作的執行次數，為算法的時間復雜度
例1：
計算Func1中++count執行的次數
void Func1(int N)
{int count = 0;for(int i = 0; i < N; ++i){for(int j = 0; j < N; ++j){++count;}}for(int i = 0; i < 2 * N; ++i){++count;}int M = 10;while(M--){++count; }printf("%d\n", count);
}Func1的基本操作次數：F(N) = N^2 + 2 * N + 10來分析一下是為什么？
首先可以看到這段代碼有三個循環
第一個是由兩個for內外嵌套組成：每次循環N次，執行了N次，即N + N + N.....=N * N = N^2 次
第二個循環執行了 2*N 次
第三個循環執行了 10 次
如果每個時間復雜度都要這么表示的話那太復雜了，所以我們只取最大量級來表示這段代碼的時間復雜度
當N? = 10時：F(N) = 130
當N = 20時：F(N) = 10210
當N = 30時：F(N) = 1002010
當我們的N取無窮大時 2 * N + 10這兩個項對結果的影響已經不大了可以忽略不計，所以說只需要取N^2來表示它的時間復雜度就可以了
所以這段代碼Func1的時間復雜度為: O(N ^ 2)
2.大O的漸進表示法
大O符號(Big O notation)：是用于描述函數漸進行為的數學符號
推導大O階方法：
（1）.用常數1來取代運行時間中的所有加法常數
（2）.在修改后的運行次數的函數中，只保留最高階項
（3）.如果最高階存在且不是1，則去除與這個項目相乘的常數，得到的結果就是大O階
通過上面一個例子我們可以發現大O漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數
我們來計算幾道代碼的時間復雜度
例1：
void Func2(int N)
{int count = 0;for(int i = 0; i < 2 * N; i++){++count;}int M = 10;while(M--){++count; }printf("%d", count);
}F(N) = 2 * N +10
去掉與最高階相乘的常熟和10使用大O漸進法表示法該段代碼的時間復雜度為：O(N)
例2：
void Func3(int M, int N)
{int count = 0;for(int i = 0; i < M; i++){++count;}for(int j = 0; j < N; j++){++count;}printf("%d\n", count);
}使用大O漸進法表示法該段代碼的時間復雜度為：O(N + M)
因為M和N是未知的所以不能去掉它們兩個任意一個
如果N大于M，則可以去掉M，反之可以去掉N，相等可任取M和N中任何一個
例3：
void Func4(int N)
{int count = 0;for(i = 0; i < 100: i++){++count;}printf("%d\n", count);
}F(N) = 100
執行了100次，但是我們用1來表示
使用大O漸進法表示法該段代碼的時間復雜度為：O(1)??
注：這里的1表示代表1次，而是常數次
3.時間復雜度的最好，最壞和平均情況
另外有些算法的時間復雜度存在最好，平均，最壞情況：
最壞情況：任意輸入規模的最大運行次數(上界)
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模最小運行次數(下界)
例4：
char* strchr(const char * str, int character)
{while(*Str){if(*str == character){return str;}str++;}return NULL;
}例如：在一個長度為N的數組中找一個數據x
最好情況：1次找到
平均情況：N/2次找到
最壞情況：N次找到
在實際情況中一般關注的是算法的最壞運行情況，所以該段代碼的時間復雜度為：O(N)
例5：
void BubbleSort(int *a, int n)
{assert(a);for(int end = n; end > 1; --end){for(int i = 1; i < end; i++){if(a[i - 1] > a[i]){int tmp = a[i];a[i] = a[i + 1];a[i + 1] = tmp;}}}
}最好情況：O(N)
最壞情況將兩個for循環跑滿
外循環為n時，內循環循環n - 1次? 然后按順序n - 2, n-3, ....., 3,?2,?1通過判斷可以知道這是一個等差數列，所以它的總和就為：n(n - 1 + 1)/2 = n^2*1/2 即最壞情況：O(N^2)
使用大O漸進法表示法去掉常數該段代碼的時間復雜度為：O(N^2)??
例6：
在數組有序的情況下：可以使用二分法（折半查找）
int binarysearch(int *a，int n, int x)
{int begin = 0;int end = n - 1;while(begin <= end){int mid = begin + ((end - begin)>>1);if(a[mid] > x){end = a[mid] - 1;}else if(a[mid] < x){begin = a[mid] + 1;}else{return mid;}}return -1;
}最好情況：O(1)
最壞情況：區間縮放到一個值，要么找到，要么找不到，假設N為數組個數，x是最壞查找次數N每次除2就等于查找一次，折半查找多少次就除多少個2
N/2/2/2..../2 = 1, 因為n為int所以最小二分到1，2^x = N 即：x = logN（log在時間復雜度中表示以2為底）所以最壞情況：O(logN)
例7：
long long fac(size_t N)
{if(N == 0)return 1;elsereturn fac(N - 1) * N;
}使用大O漸進法表示法該段代碼的時間復雜度為：O(N)
例8：
long long Fib(int n)
{if(n < 3){return 1;}else{return Fib(n - 1) + Fib(n - 2);}
}最好情況：O(1)
可以觀察到該遞歸的方式為等差數列我們用求和公式可以得出：2^(N-1)-1
最壞情況用大O漸進表示法：O(2^N)
總結以上時間復雜度：O(1)>O(logN)>O(N)>O(N^2)>O(N^3)>O(2*N)
