什麼是演算法

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

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

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

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