更多課程 選擇中心
        Java培訓

        400-111-8989

        Java培訓 > Java教程  > 正文

        程序員不要跟算法過不去!算法技術總結

        • 發布:Java培訓
        • 來源:Java教程
        • 時間:2018-01-24 11:19

        程序員不要跟算法過不去!算法技術總結

        算法

        即計算的方法,使用計算的思想、方法、工具和技術來實現問題求解的思路和途徑。計算機提供了計算的能力和硬件設施;算法則提供了計算的思想和軟件技術,更好地發揮計算機的潛能。

        有人說,算法無用,這種觀點就如同盲人看不到花開就說世界上沒有花一樣,是一個長眼睛的人無論如何也難以接受的。

        舉個簡單的例子:

        假如你要對1000,000條記錄進行排序,你的計算機每秒可處理1000,000 條記錄。

        如果你選擇 O(nlogn)的快速排序,所花時間大約是 log2(1000000) = 20s;

        如果你選擇O(n^2)的插入排序,所花時間大約是 1000000^2/1000000 = 1000000s = 11.57天;

        如果你選擇O(n^3)的XX排序,所花時間大約是1000000^2 = 31709.791年。

        很明顯,擁有子彈的不如擁有導彈的,擁有導彈的不如擁有核彈的。你很容易就可以知道,誰才是未來世界的王者。

        算法大師Knuth曾說過:“……算法作為一種一般的智能性工具,有助于對各學科知識的理解……只有將知識教給計算機,才能真正理解知識……比起常規的問題理解來說,將知識表述成算法的形式將使理解更為深刻……”

        所以,算法不僅可以決定統治世界的王者(除非你將世界上的所有計算機全部銷毀),還可以有助于個人的知識學習和理解,甚至,對生活的領悟;算法有助于高效工作的學習工作。

        程序員不要跟算法過不去!算法技術總結

        現在,就讓我們來梳理一下常用的算法設計技術吧!

        一、 分治法:

        將問題實例 P(n) 分解為 b 個子問題實例 P(n/b) , 其中有 a 個子問題需要求解。 然后將子問題的解合并起來得到原問題的解。

        一言以蔽之, 即“分而合之”。

        例子:

        ① 歸并排序: 將待排序列表先分成若干的子列表,分別排序,然后合并起來。

        ——歸并排序的關鍵在于“合”的過程;

        ② 快速排序: 選取列表中的某種元素,放在列表中的某個位置,使列表分為小于該元素和不小于該元素的兩個子列表。

        然后,分別對兩個子列表重復上述步驟,直到整個列表有序為止。

        ——快速排序法 關鍵在“分”的過程。

        ③ 二叉樹遍歷: 分別遍歷根結點、左子樹和右子樹。

        ——具有天然的分治和遞歸特性。

        分治法的效率:

        T(n) = aT(n/b) + f(n) , 其中 f(n) 是“分”或者“合”的過程中所耗費的時間。

        對于歸并排序來說, f(n) 是將兩個有序列表合并成一個更大的有序列表所耗費的時間;對于快速排序來說, f(n) 是選取分割元素并將其放在最終位置所耗費的時間。

        根據主定理: 令 f(n) = O(n^d),

        ① 當 d > log(a)/log(b) 時, T(n) = n^d;

        ② 當 d = log(a)/log(b) 時, T(n) = (n^d)log(n)

        ③ 當 d < log(a)/log(b) 時, T(n) = n^(log(a)/log(b))

        主定理其實很好記: T(n) 的效率由 aT(n/b) 和 f(n) 的效率比較而得,其中 aT(n/b) 的效率可看成: ^(log(a)/log(b)),只要比較冪數取大者就可以了。

        常用的分治法,是將問題實例分成規模大致相等的2個子問題實例。

        根據主定理:

        T(n) = 2T(n/2) + O(C) , C 是常數 --------- T(n) = O(n)

        T(n) = 2T(n/2) + n ----- T(n) = O(nlog2(n))

        T(n) = 2T(n/2) + n^2 ------------------- T(n) = O(n^2)

        可以看出, f(n) 也是起很重要作用的, f(n) 不能太大, 最好是線性的,否則, 采用分治法的效率就可能不高了。合理采用分治法的效率一般應該可以達到O(nlog2(n)),至少應該比采取其他算法技術的效率要高一個級別。

        二、減治法:

        當 a = 1 時, 即 T(n) = T(n/b) + f(n) 時, 分治法就退化為減治法。 此時,f(n) 的大小就起非常重要的影響了。

        減治法有三種形式:

        ① 減常量: T(n) = T(n-b) + f(n) eg.

        T(n) = T(n-1) + C, C為常數 ----- T(n) = O(n)

        T(n) = T(n-1) + n ----------- T(n) = O(n^2)

        減常量的例子: 插入排序 ----- T(n) = T(n-1) + n T(n) = O(n^2)

        ② 減常因子: T(n) = T(n/b) + f(n), eg.

        T(n) = T(n/2) + C, C為常數 ------ T(n) = O(log2(n)) 折半查找

        T(n) = T(n/2) + n ---------------- T(n) = O(n^2)

        ③ 減可變規模: 例如 求最大公約數 gcd(m,n) = gcd(n, m%n)

        總之,在使用分治法或者減治法時,應當合理地進行子問題分割,盡量使分和合的過程簡單, 使 f(n) 保持線性,這樣,才能達到分治法和減治法的高效。

        三、動態規劃法

        動態規劃法的解通常具有如下遞推形式: S(n) = G(S(n-i) , f(n)) i = 1,2,……,n 其中 S(n-i) 和 S(n-j) 往往具有重合的子問題 S(n-k), k>i,k>j,此時,可以采用自底向上的迭代法或基于記憶功能的遞歸法來一步步地構造解S(1),S(2),……,S(n)。

        由于避免了對子問題的重復求解,因此,動態規劃法顯示出了比較高的效率。

        動態規劃法與分治法的區別: 分治法所分成的子問題實例通常沒有重合的子問題實例,而動態規劃法所分成的子問題實例通常有重合的地方,而且,動態規劃法的最優解往往蘊含著子問題實例的最優解,因此,可以由子問題實例的最優解逐步構造最終的最優解。

        動態規劃法的典型例子: 求斐波那契數列、求二項式系數、背包問題、最長子序列問題、矩陣連乘問題。

        四、變治法

        變治法基于問題轉化的思想,將所要求解的問題實例轉化為更為特殊形式的問題實例,或者已被求解的其它問題實例。變治法要求對問題之間的聯系具備非凡的洞察力。

        典型的變治法包括預排序。將待處理列表先進行排序,然后再對有序列表進行其它處理。

        比如查找問題,如果采用順序查找,則需要O(n)的時間,而先排序后二分查找,則需要至少O(nlog2(n)),顯然,預排序似乎是多余的。

        不過,如果要進行多次查找,則預排序就開始起作用了。假設要對1000條記錄進行 C 次查找, 則有 Cn > nlog2(n) + Clog2(n), n=1000 可解得 C > 10.

        也就是說,僅僅要查找十次以上,預排序就開始起作用了。

        另一個變治法的簡單例子是求解最小公倍數lcm(m,n)。

        如果你知道 lcm(m,n) = m*n/gcd(m,n) , gcd(m,n) 是最大公約數,有一個非常高效的歐幾里得算法,那么,這個問題就顯得容易得多了。

        前提是,你要能夠具備豐富的知識和良好的洞察力。該問題的最簡單的算法是,從1開始,1,2,……,n, 逐個計算直到能被m和n整除為止。效率為 O(mn); 較好的算法是,取其中最大數 max = max(m,n), 從1開始,逐個進行相乘,max, 2max,……,kmax, 直到能被n 整除位置,效率為 O(min(m,n))。

        采用變治法往往可以收到意想不到的效果。要善于進行問題分析,轉化問題。

        五、 時空權衡

        時空權衡基于“空間充裕廉價,時間寶貴”以及“空間極其有限,時間要求不高”的思想,要么以犧牲空間的代價換取時間的高效,要么以犧牲時間的代價換取空間的要求。前者在桌面PC領域更加常見,后者在單片機、嵌入式等產品中體現較明顯。

        典型例子:

        計數排序: 使用一個數組來存儲比元素大或者小的元素個數,根據這些值來確定元素在最終列表中的位置。

        散列法: 使用數組和鏈表的結合來實現字典的高效。首先,采用某種哈希函數hash(x) 將 基于鍵key 的記錄映射到哈希表的相應位置hashtable[hash(key)]中,如果有沖突(多個鍵的記錄被映射到同一個下標),則使用附在該下標的鏈表存儲沖突的記錄。這也是一個顯示數據結構組合應用能夠產生強大功能的令人深刻的例子。

        遞歸/非遞歸遍歷: 使用額外的棧或者標記來存儲遍歷過程中已經遍歷了的元素,從而避免重復遍歷。

        六、 貪婪技術

        總是從當前的可行選擇中選取局部最優的部分解,一步步構造最終的解。

        貪婪技術逐步構造最優解的三個條件:

        1. 可行:滿足問題的約束條件

        2. 局部最優:在當前可行的選擇中總是選擇局部最優的部分解。

        3. 不可撤銷:一旦做出選擇,就不可撤銷。

        貪婪技術的典型例子: 找硬幣、最小生成樹的 Prim算法 和 Kruskal算法 , 單起點最短路徑的 Dijskra算法。

        七、 蠻力法

        不要小看蠻力法。蠻力法總是可以找到一個解,雖然這個解通常并不實用。蠻力法的作用是,找到一個解,然后對其進行改進。蠻力法有時可以給人帶來驚喜。

        比如子字符串匹配(判斷字符串str 中是否含有子字符串pattern) 的蠻力法版本,其最差效率O(mn),平均效率為O(m), m,n 分別是 str 和 pattern 的長度。也就是說,蠻力法版本的子字符串匹配算法是比較實用的。

        蠻力法的典型例子: 排列組合問題的窮舉查找法。

        八、 迭代改進

        迭代改進法,總是最先找到一個可行解,然后通過一些小的、局部的變化來改進這個可行解,使之趨向最優解。迭代改進的關鍵是穩定性、收斂性。

        迭代法的典型例子: 數值算法、遺傳算法

        九、 回溯法

        回溯法是窮舉查找法的改進版本,窮舉查找法通常先列舉出所有的候選解,然后根據目標問題來找出滿足要求的解或最優解。而回溯法則“聰明”了一些,一步一步地構造解的分量,一旦有分量不可行,則此路不通,馬上轉道。回溯法通常根據問題構造一棵狀態樹,通過遍歷狀態樹的結點來求解。葉子節點代表無解或可行解。

        回溯法的典型例子: n 皇后問題,圖的深度遍歷

        十、 分枝定界技術

        分枝定界技術與回溯法非常相似。由于我還沒有學到這里,因此,暫不作討論。分枝定界技術常用來求解最優化問題。

        十一、 求近似解

        退而求其次,不失為一種明智的選擇。如果花20分鐘可以獲得旅行商問題的實用解,那么,再多花十個小時,使解獲得0.1%的改進,是否有必要?對于理論工作者來說,確實如此。但如果是實踐工作者,我會選擇前者。要學會權衡投資/收益比。

        結語:

        總結算法,應用算法。算法,當之無愧是計算機科學的靈魂和基石。無論是硬件還是軟件,無論是專業還是生活,算法無處不在。

        不能因為暫時用不到就貶低它的價值,——事實上,這是一種掩耳盜鈴的做法。你不用,別人總會用的,而且,別人可以從中體驗樂趣,獲取豐厚的回報。千萬不要跟算法過不去。

        感謝大家閱讀由java培訓機構分享的“程序員不要跟算法過不去!算法技術總結”希望對大家有所幫助,更多精彩內容請關注Java培訓官網

        免責聲明:本文由小編轉載自網絡,旨在分享提供閱讀,版權歸原作者所有,如有侵權請聯系我們進行刪除

        預約申請免費試聽課

        填寫下面表單即可預約申請免費試聽!怕錢不夠?可就業掙錢后再付學費! 怕學不會?助教全程陪讀,隨時解惑!擔心就業?一地學習,可全國推薦就業!

        上一篇:年薪50萬的Java EE學習路線圖,快學起來~
        下一篇:Java編碼易疏忽的十個問題
        12大要點讓你的Java開發所向披靡~

        12大要點讓你的Java開發所向披靡~

        學習Java最好的12本免費在線電子書

        學習Java最好的12本免費在線電子書

        Java常用日志框架介紹

        Java常用日志框架介紹

        一篇文章了解RPC框架原理

        一篇文章了解RPC框架原理

        • 掃碼領取資料

          回復關鍵字:視頻資料

          免費領取 達內課程視頻學習資料

        • 視頻學習QQ群

          添加QQ群:1143617948

          免費領取達內課程視頻學習資料

        Copyright ? 2021 Tedu.cn All Rights Reserved 京ICP備08000853號-56 京公網安備 11010802029508號 達內時代科技集團有限公司 版權所有

        選擇城市和中心
        貴州省

        福建省

        • 達內廈門軟件園中心
        廣西省

        海南省

        国产高清情侣视频2019年,限制电影福利在线观看,23伊人大香蕉 百度 好搜 搜狗
        <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>