演算法中的時間頻度與時間復雜度
時間頻度
一個演算法花費的時間與演算法中陳述句的執行次數成正比例，哪個演算法中陳述句執行次數多，它花費時間就多，一個演算法中的陳述句執行次數稱為陳述句頻度或時間頻度，記為T(n)
時間復雜度
一般情況下，演算法中的基本操作陳述句的重復執行次數是問題規模 n 的某個函式，用 T(n)表示，若有某個輔助函式 f(n)，使得當 n 趨近于無窮大時，T(n) / f(n) 的極限值為不等于零的常數，則稱 f(n)是 T(n)的同數量級函式，記T(n)=Ｏ( f(n) )，稱Ｏ( f(n) ) 為演算法的漸進時間復雜度，簡稱時間復雜度；
T(n) 不同，但時間復雜度可能相同， 如：T(n)=n2+7n+6 與 T(n)=3n2+2n+2 它們的 T(n) 不同，但時間復雜
度相同，都為 O(n2）
計算時間復雜度的方法：
-
用常數 1 代替運行時間中的所有加法常數 T(n)=n2+7n+6 => T(n)=n2+7n+1
-
修改后的運行次數函式中，只保留最高階項 T(n)=n2+7n+1 => T(n) = n2
-
去除最高階項的系數 T(n) = n2 => T(n) = n2 => O(n2)
常見的時間復雜度
常數階 O(1)
對數階 O(log2n）
線性階 O(n)
線性對數階 O(nlog2n）
平方階 O(n^2)
立方階 O(n^3)
k 次方階 O(n^k)
指數階 O(2^n)
常見的演算法時間復雜度由小到大依次為：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n)
隨著問題規模 n 的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低;
我們應該盡可能避免使用指數階的演算法
StringBuffer和StringBuilder
前面所學習的string類是不可變的字符序列，而StringBuffer和StringBuilder非常類似，均代表可變的字符序列；
StringBuffer 執行緒安全，做執行緒同步檢查， 效率較低；
StringBuilder執行緒不安全，不做執行緒同步檢查，因此效率較高；
在平時的專案中一般采用高效率的StringBuilder類；
String Builder常用方法
多載的public StringBuilder append(…)方法
可以為該StringBuilder 物件添加字符序列，仍然回傳自身物件；
方法 public StringBuilder delete(int start,int end)
可以洗掉從start開始到end-1為止的一段字符序列，仍然回傳自身物件；
方法 public StringBuilder deleteCharAt(int index)
移除此序列指定位置上的 char，仍然回傳自身物件；
多載的public StringBuilder insert(…)方法
可以為該StringBuilder 物件在指定位置插入字符序列，仍然回傳自身物件；
方法 public StringBuilder reverse()
用于將字符序列逆序，仍然回傳自身物件；
方法 public String toString()
回傳此序列中資料的字串表示形式；
值得注意的是：
當我們需要對一個字串追加序列時一般采用append方法用來減少記憶體的使用和提高運行效率；
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272172.html
標籤：其他