1.算法效率
2.時間復雜度
3.空間復雜度
4. 常見時間復雜度以及復雜度oj練習
1.算法效率
1.1 如何衡量一個算法的好壞
如何衡量一個算法的好壞呢？比如對于以下斐波那契數的計算
long long Fib(int N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}
我們看到雖然用遞歸的方式實現斐波那契很簡單，但是簡單一定代表效率高嗎？
我們接著往下看。
1.2 算法的復雜度
算法在編寫成可執行程序后，運行時需要耗費時間資源和空間(內存)資源 。因此衡量一個算法的好壞，一般
是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。
時間復雜度主要衡量一個算法的運行快慢，而空間復雜度主要衡量一個算法運行所需要的額外空間。在計算
機發展的早期，計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經過計算機行業的迅速發展，計
算機的存儲容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個算法的空間復雜度。
1.3 復雜度在校招中的考察
我們可以看到在校招筆試的時候可能會遇到一些問題，就是它限制了時間和空間的復雜度，這無疑是加大了難度，所以我們現要了解什么是時間和空間復雜度，這樣才能去寫這道題。
2.時間復雜度
2.1 時間復雜度的概念
時間復雜度的定義：在計算機科學中，算法的時間復雜度是一個函數，它定量描述了該算法的運行時間。一
個算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知
道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復雜度這個
分析方式。一個算法所花費的時間與其中語句的執行次數成正比例，算法中的基本操作的執行次數，為算法
的時間復雜度。
即：找到某條基本語句與問題規模N之間的數學表達式，就是算出了該算法的時間復雜度。
// 請計算一下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 k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}
通過我們的精確計算，count總共經過了N^2+2*N+M.
Func1 執行的基本操作次數 ：
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010
所以當N特別大的時候后面可以忽略掉。
所以上面的代碼的時間復雜度是O（N^2）.
實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要大概執行次數，那么這
里我們使用大O的漸進表示法。
2.2 大O的漸進表示法
大O符號（Big O notation）：是用于描述函數漸進行為的數學符號。
推導大O階方法：
1、用常數1取代運行時間中的所有加法常數。
2、在修改后的運行次數函數中，只保留最高階項。
3、如果最高階項存在且不是1，則去除與這個項目相乘的常數。得到的結果就是大O階。
使用大O的漸進表示法以后，Func1的時間復雜度為O(N^2).
通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數。
另外有些算法的時間復雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規模的最大運行次數(上界)
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數(下界)
例如：在一個長度為N數組中搜索一個數據x
最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到
在實際中一般情況關注的是算法的最壞運行情況，所以數組中搜索數據時間復雜度為O(N)
2.3常見時間復雜度計算舉例
// 計算Func2的時間復雜度？
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);
}
這個count的準確次數是2*N+M
所以寫成大O是O（N）。
2
// 計算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);
}
這里就要看前提是什么，如果不知道M和N的話，我們就可以寫成O（M+N），如果M和N一樣的話，可以寫成O（N），如果N比M大的多，就可以寫成O（N），反之則為O（M）。
// 計算Func4的時間復雜度？
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}
常數項其實就是O（1）因為我們的計算機的運行速度特別快，每秒十幾億的速度，所以常數項都可以寫成O（1）.
// 計算strchr的時間復雜度？
const char * strchr ( const char * str, int character );
意思就是找一個字符，有就返回字符位置，沒有就返回空指針，所以這肯定要遍歷一遍我們的字符串，所以是O（N）。
// 計算BubbleSort的時間復雜度？
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個數，那第一次要比較的是n-1次，接下來，比如我們是升序的話，最后一個數就排好了，并且是最大的一個數，所以第二次就可以忽略最后一個數的比較，接下來就是n-2，這樣下去一直到1，所以將他們相加，是（N^2-N）/2,當N無窮大的時候，所以大O就可以寫成O（N*N）.最快只需要n-1次就可以了
// 計算BinarySearch的時間復雜度？
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;elsereturn mid;}return -1;
}我們的二分查找時間復雜度可快了，是效率非常高的一個排序。
它的算法時間復雜度是O（log2N）,可以寫成logN，底數是2.
為什么說他快呢，舉個例子，比如我們要在14億人中要找出有個人，最壞情況只要31次，第一次直接去掉了7億人，第二次又是一半，所以效率快。
//計算階乘遞歸Fac的時間復雜度？
long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}
其實它遞歸了N次，那就很簡單，就是O（N）。
// 計算斐波那契遞歸Fib的時間復雜度？
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}
通過計算分析發現基本操作遞歸了2N次，時間復雜度為O(2N)，因為我們第一次是2的1次，后面就是2的2次，一直到2的n次，相加就可寫成O（2^N）,所以遞歸并不是效率特別高的算法有時候，但是它簡潔。
今天的分享就到這里，我們下次再見
)
