什麼是演算法

1、2022/2/21演算法 第一章1介紹介紹12022/2/21演算法 第一章1-2什麼是演算法？ n演算法是解決一個問題的流程n這個流程必須定義得很明確n而且可能會需要一些輸入n並且會產生一些輸出 2022/2/21演算法 第一章1-3為什麼要學演算法？ n我們有 32 個外觀看起來都一樣的硬幣，其中有一個是劣幣而且其重量與其他 31 個不同（輕或重都可能）n請找出這個劣幣，並且決定它是比真幣輕或是重n唯一能使用的工具是一支天秤n每一次天秤量過的結果包括：左邊這一組硬幣的重量小於、等於、或大於右邊這一組硬幣的重量。 2022/2/21演算法 第一章1-4直覺的解法演算法1.1 2022/2/2

2、1演算法 第一章1-5直覺的解法演算法1.1n演算法 1.1 所需要使用的天秤次數跟輸入的硬幣數目成正比n換句話說，如果輸入的硬幣數有 n 個，那麼演算法 1.1 所需要使用的天秤次數跟 n 成正比2022/2/21演算法 第一章1-6聰明人花一星期想出的演算法 2022/2/21演算法 第一章1-7聰明人花一星期想出的演算法 2022/2/21演算法 第一章1-8聰明人花一星期想出的演算法 2022/2/21演算法 第一章1-9聰明人花一星期想出的演算法 n淘汰與搜尋法n所需要使用的天秤次數跟 log2 n 成正比 2022/2/21演算法 第一章1-10學過演算法後設計出的演算法 2022

3、/2/21演算法 第一章1-11學過演算法後設計出的演算法2022/2/21演算法 第一章1-12為什麼要學演算法？n演算法 1.1 是沒學過演算法的普通人設計出的n演算法 1.2 則是沒學過演算法的聰明人所絞盡腦汁設計出的n演算法 1.3 則是學過演算法的普通人或聰明人設計出的n不管我們是普通人或聰明人，只要修學過演算法，我們所設計出來的演算法可以比聰明人（但是沒學過演算法）絞盡腦汁後所設計出的演算法還好！ 2022/2/21演算法 第一章1-13更多必須修學演算法的理由 2022/2/21演算法 第一章1-14更多必須修學演算法的理由n圖論證明 n 個頂點的圖裡最多可以找出nn-2 棵生成

4、樹n當 n = 100 時，nn-2 等於 10196！ n這個問題只要用貪婪法就可以很簡單地在 n2 的時間複雜度下解決掉 2022/2/21演算法 第一章1-15更多必須修學演算法的理由n凸面體 2022/2/21演算法 第一章1-16更多必須修學演算法的理由n一般人面對這個問題可能無從著手n如果你修學過演算法就知道這個問題只要用貪婪法就可以在 n log n 的時間複雜度下解決掉。 2022/2/21演算法 第一章1-17更多必須修學演算法的理由n看起來很簡單，實際上卻是很難的問題2022/2/21演算法 第一章1-18更多必須修學演算法的理由nNP-完備問題n到目前為止，所有的 NP-完備問題都還找不到任何有效率的演算法！2022/2/21演算法 第一章1-19更多必須修學演算法的理由n0/1打包問題 n公司裡有 n 個不同的物品，物品 i 所佔用的體積是 vi 而價值為 pi，大保險櫃的容量則是 Cn針對每一項物品，我們只能選擇放入大保險櫃或者不放入大保險櫃n我們的目標是使得大保險櫃中所放置的物品總價值最大，前提是所放置的物品總體積不能超過大保險櫃的