# 算法時間復雜度分析法
分析一個算法的時間復雜度有兩種情況可以分析
1.寫完之后看執行時間（事后分析估算方法:）
2.分析算法函數，得出算法時間復雜度（事前分析估算方法:）
**事后分析估算方法:**
比較容易想到的方法就是我們把算法執行若干次，然后拿個計時器在旁邊計時，這種事后統計的方法看上去的確不 錯，并且也并非要我們真的拿個計算器在旁邊計算，因為計算機都提供了計時的功能。這種統計方法主要是通過設 計好的測試程序和測試數據，利用計算機計時器對不同的算法編制的程序的運行時間進行比較，從而確定算法效率 的高低，但是這種方法有很大的缺陷:必須依據算法實現編制好的測試程序，通常要花費大量時間和精力，測試完 了如果發現測試的是非常糟糕的算法，那么之前所做的事情就全部白費了，并且不同的測試環境(硬件環境)的差別 導致測試的結果差異也很大。
```
//可以直接通過時間差計算方法執行時間
static function getFunExTime(){
$t1=microtime(true);
for( $i=1;$i<=10000;$i++){
echo $i."*";
}
echo "<br>";
$t2=microtime(true);
echo $t1."<br>";
echo $t2."<br>";
echo "消耗時間：".round($t2-$t1,3);
}
```
**事前分析估算方法:**
很多時候，我們并不在算法實現之后再來對算法進行估算，我們需要在編寫之前就對我們的算法進行估算。經過總結，我們發現一個高級語言編寫的程序程序在計算機上運行所消耗的時間取決于下列因素:
1.算法采用的策略和方案;
2.編譯產生的代碼質量;
3.問題的輸入規模(所謂的問題輸入規模就是輸入量的多少);
4.機器執行指令的速度;
**算法分析:**
由此可見，拋開這些與計算機硬件、軟件有關的因素，一個程序的運行時間依賴于算法的好壞和問題的輸入規模。
如果算法固定，那么該算法的執行時間就只和問題的輸入規模有關系了。
那么再次以之前的求和案例為例，進行分析。
**需求:計算1到100的和。**
解法1：
```
//如果輸入量為n為1，則需要計算1次;
//如果輸入量n為1億，則需要計算1億次;
public function get100Sum(){
$sum=0;
$n=100;
for ($i=1; $i=$n < ; $i++) {
$sum+=$i;
}
echo "1到100的和是：".$sum;
}
```
解法2:
```
//如果輸入量為n為1，則需要計算1次;
//如果輸入量n為1億，則需要計算1次;
public function getSum100(){
$sum=0;
$n=100;
$sum = ($n+1)*$n/2
echo "1到100的和是：".$sum;
}
```
因此，當輸入規模為n時，第一種算法執行了1+1+(n+1)+n=2n+3次;第二種算法執行了1+1+1=3次。如果我們把 第一種算法的循環體看做是一個整體，忽略結束條件的判斷，那么其實這兩個算法運行時間的差距就是n和1的差距。
為什么循環判斷在算法1里執行了n+1次，看起來是個不小的數量，但是卻可以忽略呢?我們來看下一個例子:
**需求: 計算100個1+100個2+100個3+...100個100的結果**
代碼：
```
static function fun1(){
$sum=0;
$j=100;
for($s = 1;$j<=$n;$s++){
for ($b=1;$b<=$j;$b++) {
$sum +=$b;
}
}
}
```
上面這個例子中，如果我們要精確的研究循環的條件執行了多少次，是一件很麻煩的事情，并且，由于真正計算和
的代碼是內循環的循環體，所以，在研究算法的效率時，我們只考慮核心代碼的執行次數，這樣可以簡化分析。
我們研究算法復雜度，側重的是當輸入規模不斷增大時，算法的增長量的一個抽象(規律)，而不是精確地定位需要 執行多少次，因為如果是這樣的話，我們又得考慮回編譯期優化等問題，容易主次跌倒。
我們不關心編寫程序所用的語言是什么，也不關心這些程序將跑在什么樣的計算機上，我們只關心它所實現的算
法。這樣，不計那些循環索引的遞增和循環終止的條件、變量聲明、打印結果等操作，最終在分析程序的運行時間
時，最重要的是把程序看做是獨立于程序設計語言的算法或一系列步驟。我們分析一個算法的運行時間，最重要的
就是把核心操作的次數和輸入規模關聯起來。
