上一篇博客已經給大家介紹了一些演算法題，明天剛好是中秋了，這裡祝大家中秋快樂。剛好趕上數學建模了，今天就先介紹與衡量演算法水平的重要指標時間複雜度吧。在時間充裕情況下會更新5+2。之後還會介紹空間複雜度以及python內置函數的時間複雜度。 1.簡介 先看一下什麼是時間複雜度： 衡量代碼的好壞，包括兩個 ...
上一篇博客已經給大家介紹了一些演算法題，明天剛好是中秋了，這裡祝大家中秋快樂。剛好趕上數學建模了，今天就先介紹與衡量演算法水平的重要指標時間複雜度吧。在時間充裕情況下會更新5+2。之後還會介紹空間複雜度以及python內置函數的時間複雜度。
1.簡介
先看一下什麼是時間複雜度：
衡量代碼的好壞，包括兩個非常重要的指標：
運行時間和占用空間。
代碼的絕對執行時間是無法估計的，但可以預估代碼的基本執行次數。
2.程式中最常見的四種執行方式有
(1)T(n) = kn，執行次數是線性的。
可以理解為有一個任務，完成全部要達到n，每k個時間完成任務的1/n，則完成全部任務所需要的時間為kn個時間。
(2)T(n) = klog(a)(N)，執行次數是對數的。
可以理解為有一個任務，完成全部要達到n，每k個時間完成任務的1/a，然後下一個時間完成剩下任務的1/a，依次迴圈，則完成全部任務所需要的時間為kloa(a)N個時間。
(3)T(n) = k，執行次數是常量的。
可以理解為有一個任務，完成全部要達到n，則k個時間完成任務的n，也就是需要k個時間完成所有任務，這個是可以得到代碼的絕對執行時間的，則完成全部任務所需要的時間為k個時間。
(4)T(n) = 0.5n^2 + 0.5n，執行次數是一個多項式。
可以理解為有一個任務，完成全部要達到n，完成第一個1要1個時間，完成第二個1要2個時間，就是不斷相加，這裡簡化了，則完成全部任務所需要的時間為0.5n^2 + 0.5n個時間。
(5)時間複雜度
但是上面的不同情況的由於演算法不同無法比較，而且有時候根據n的取值比較結果也不同。這時候就有了漸進時間複雜度的概念：
若存在函數 f（n），使得當n趨近於無窮大時，T（n）/ f（n）的極限值為不等於零的常數，則稱 f（n）是T（n）的同數量級函數。
記作 T（n）= O（f（n）），稱O（f（n）） 為演算法的漸進時間複雜度，簡稱時間複雜度，也被稱為大O表示法。
(6)時間複雜度的規則
如果運行時間是常數量級，用常數1表示；
只保留時間函數中的最高階項；
如果最高階項存在，則省去最高階項前面的繫數。
就是當運行時間不是常數時，省去前面的k繫數。
一般常見的時間複雜度的比較為：O（1）< O（logn）< O（n）< O（n^2）
