聽說讀寫

摘要： 算法面試題中經常出現的一種題目就是 查找 或者是排序. 個人感覺有80%的題目都和查找排序有關大部分常用的排序算法時間復雜度都是O(nLogn)這個只能說是通用解,一般解對于算法面試題中往往要求很低的時間復雜度,例如下面這個題目已知一個數組長為m 中間存放的都是整數 其值范圍為1-m ,中間的元素有可能重復 也有可能不重復如何在O(M)的情況下查到 (1-m)的數中 哪些數重復了,哪些數沒有出現counting sort 的本質是 新建一個長度為M的數組An 每一個數組下標代表一個數,數組中的值代表這個元素出現的次數 (初始值都為0)那么, 遍歷一次m 遇到一個數 就在對應的下標上加1那么最終 閱讀全文

摘要： 排序算法 時間復雜度 最差時間復雜度冒泡 O(n*n)插入 O(n*n)選擇 O(n*n)歸并O(nLogn)堆 O(nLogn)快速O(nLogn) O(n*n) 一般來說 最常用的排序是快速排序 ,實現簡單 效率快, 對比對排序和歸并排序, 快速排序的系數比較小,所以都是NlogN的時候會比較快PS: 在數據量比較小的時候最好別用歸并排序...不過數據量小的時候這個時間無所謂啦在大數據量或者特殊情況或者特別優化的情況下 還是有算法比快速排序快的 只是比較少遇到PS2:已經有很多證明,比較排序的時間復雜度不可能低于nLogn最近難得有空重新拿起算法導論看一遍..blog這里就當作筆記吧... 閱讀全文