算法分析
01、概述定义
http://pic2.zhimg.com/v2-bcf574c3e54b52cba9dec5f4833970b5_r.jpg
http://pic3.zhimg.com/v2-87a7679b75d77729bb6845d3bbd25d36_r.jpg
算法 != 计算
http://pic1.zhimg.com/v2-e197782583757c4ccbc926cf3c15e4c4_r.jpg
最早的算法：求最大公因子
http://pic3.zhimg.com/v2-8a6ac884d0df086b71c48f48e3ab7af2_r.jpg
算法面向一个问题，而不是一个两个实例。
算法是CS基础的重要主题。—— The Art of Computer Programming 7卷
分析
http://pic1.zhimg.com/v2-381c378a84b7e6d2d144c47a98800ad0_r.jpg
http://pic2.zhimg.com/v2-93133d0dc2e6ee6fe945682b65212ff1_r.jpg
P：确定图灵机
NP：非确定图灵机多项式时间内能否解决？
单独的复杂性类：图的同构等等...
http://pic2.zhimg.com/v2-fa10545fa41ac4b50ed5ca9a22413591_r.jpg
算法分析：分析而不是实验
正确性
http://pic3.zhimg.com/v2-66451b5eb4e1cd0dda1760a5084636ce_r.jpg
http://pic1.zhimg.com/v2-3876ebde8dcb8d4d9f4312b879c0c474_r.jpg
正确性需要严格证明：
http://pic2.zhimg.com/v2-bb6130c3874acec3ef79a2e853235351_r.jpg
复杂性
大数据耗电已经不能忽略电费啦！
http://pic2.zhimg.com/v2-95efcbc8a5775804518a2c1ddc0a85b9_r.jpg
http://pic2.zhimg.com/v2-436475b4b1709be6f14c32823bebe95d_r.jpg
http://pic4.zhimg.com/v2-62f452c4d02743f51319ae50264f32cb_r.jpg
http://pic4.zhimg.com/v2-b99a44a647eb9f61db9d733914b2f217_r.jpg
http://pic3.zhimg.com/v2-58e6432b3eed9f1588c328d303324886_r.jpg
虽然分析平均复杂性比较好，但是概率是假设的。
http://pic1.zhimg.com/v2-89dc180190f47f3830a1bd43d42a59e4_r.jpg
并行：多核、MapReduce
http://pic4.zhimg.com/v2-812850a72db6854601c6b48b21165923_r.jpg
http://pic1.zhimg.com/v2-ea44d28e6518c1433017f395ec484c38_r.jpg
算法设计
http://pic2.zhimg.com/v2-4a5f3cd4218a8e499987ec4ef958f3c9_b.jpg
[*]暴力遍历
[*]分而治之
[*]图：分支、回溯
[*]随机化方法
http://pic3.zhimg.com/v2-1ed11f5d2c730a45cbbc5cc9cfbd9752_r.jpg
02、数学基础
http://pic2.zhimg.com/v2-db08b7257897f62cc860d8d1d25f1d21_r.jpg
《具体数学》、《算法分析导论》
复杂性函数的阶 —— n是输入的规模
输入的规模、机器、指令集....影响因素
渐进的阶：O、o、theta
http://pic2.zhimg.com/v2-043cf90a83f82d7616a309439c62fbcd_r.jpg
增长函数来描述阶
http://pic1.zhimg.com/v2-cc788279e1f7a3d799b5dce936f8a294_r.jpg
http://pic4.zhimg.com/v2-6dffacae6576a6d725e42e6c8f564fa3_r.jpg
描述的是，增长率的大小。
http://pic1.zhimg.com/v2-06aecf686d9df9c0e8bd03eecaa46c18_r.jpg
—— 保留高阶项，忽略低阶。
http://pic4.zhimg.com/v2-e9c92c582cf320c088a6340e67b0399b_r.jpg
http://pic2.zhimg.com/v2-dfa6abbd39697951098c6e030b44cdd5_r.jpg
http://pic1.zhimg.com/v2-565103bd0db447f054cd483cffe0d65c_r.jpg
http://pic4.zhimg.com/v2-da658bfd0953464a4a88ebd6f6beed0f_r.jpg
数据很大时，需要设计亚线性、log算法
http://pic3.zhimg.com/v2-68b78c6fac32649ddcb32abf51fdeb6e_r.jpg
http://pic3.zhimg.com/v2-69fe2dadcaa406acb94f101c8e2b940a_r.jpg
http://pic4.zhimg.com/v2-5ddf673524e2d80dfb33a61ccce5d4cf_r.jpg
最起码
http://pic4.zhimg.com/v2-bb97c5b0f3e3a8fa14e181e9bec0e1af_r.jpg
http://pic3.zhimg.com/v2-6c396809d0b779f5cbde5b79f6a6a87a_r.jpg
重要的是找到 n0
http://pic4.zhimg.com/v2-2512765c1e6ac2527210704c59a9d28b_r.jpg
http://pic3.zhimg.com/v2-504a58df57d2d2cd4ad2c4be28a4237e_r.jpg
http://pic1.zhimg.com/v2-746a7cb86d4ec2a2bb7674b931a05cf8_r.jpg
http://pic3.zhimg.com/v2-8e58ad90f9b2d6d0c5ce707cd9ee6c02_r.jpg
和式的估计和界限：UNDONE
http://pic3.zhimg.com/v2-690936a760dfcc1462d16123fe25f062_r.jpg
数列
http://pic3.zhimg.com/v2-d03a0f37426b4e7c97a5877a3d7fcb5e_r.jpg
级数
http://pic1.zhimg.com/v2-6d8d32c3b6b30a723680637df0177d94_r.jpg
http://pic3.zhimg.com/v2-5ccb3d86d5859f97fd0be84e7104a82a_r.jpg
http://pic3.zhimg.com/v2-776474485addf5169ef6b584ebc45b72_r.jpg
递归方程：UNDONE
http://pic1.zhimg.com/v2-2614c3292d7c24566e5ae28a9196e674_r.jpg
http://pic3.zhimg.com/v2-06ee7290eead591519891a2ce44af8c6_r.jpg
03、分治算法
设计分治算法
http://pic1.zhimg.com/v2-b5314bbeb875ad12ea4cae9b482e12d4_r.jpg
例如校园分成一块一块，然后去找卖煎饼果子的，然后排除一些不可能的块，比如教室。
http://pic3.zhimg.com/v2-2c9a9e4037c5ac9cee0f3e1579d35ef2_r.jpg
划分、递归调用来求解子问题、合并 —— 如何分、合、尽可能少求解子问题。
http://pic1.zhimg.com/v2-910bf65dfa1b57dc140ce79a7d934560_r.jpg
http://pic2.zhimg.com/v2-035f9092c92af8dd715b45f7a42324f1_r.jpg
http://pic3.zhimg.com/v2-d38f50d8396fb092851ba2643905a2c6_r.jpg
例子：大整数算法
http://pic1.zhimg.com/v2-1a316406b6f185c5f63c1f6e6a18c5dc_r.jpg
http://pic4.zhimg.com/v2-133d2e40f64187cf7c2e1869b36f334f_r.jpg
http://pic1.zhimg.com/v2-185f68ab69b6342eab4353514041467c_r.jpg
http://pic3.zhimg.com/v2-d612aac6ab89fabe2b01817b257e3a5a_r.jpg
例子：最大值、最小值
http://pic1.zhimg.com/v2-42b40e95b7c787320bc0b966d538bfbc_r.jpg
类似归并排序：
http://pic1.zhimg.com/v2-c266bd43d1f0bb7005bfa152d30ef374_r.jpg
http://pic1.zhimg.com/v2-225c7f4763c4c3255f3edd0cab6b3978_r.jpg
http://pic4.zhimg.com/v2-89c8fd9c4708beccbe412acf44c71a1f_r.jpg
元素选取问题的线性时间算法
中位数：
http://pic3.zhimg.com/v2-b5a6bd612ec8fa4d5c9a0f8295900fd2_r.jpg
http://pic4.zhimg.com/v2-d2edcd19ac3d81b5b32212ce8ef488ef_r.jpg
http://pic3.zhimg.com/v2-c5ebf1b9319d1ccde92941f3956e2eea_r.jpg
变为选取第k大的问题：
http://pic4.zhimg.com/v2-4b0db7bc99e8ae352513303946d7052b_r.jpg
http://pic1.zhimg.com/v2-b7b9b9013b38e7bbceda79ee0f3ef39c_r.jpg
http://pic1.zhimg.com/v2-9a916daccc08b9e6d61a6934ae760314_r.jpg
http://pic1.zhimg.com/v2-0440437ff2d547977b0aa9b80c3e5858_r.jpg
http://pic4.zhimg.com/v2-d35ec02d9c9454d1d7abf3008182acf3_r.jpg
http://pic4.zhimg.com/v2-6b42cd1e2c0d44b36b1a0fc15b8158f7_r.jpg
http://pic3.zhimg.com/v2-8057172009be9ab3f9c834db3457420e_r.jpg
http://pic4.zhimg.com/v2-9fda270ae5df47fe3bc8b1b1d86b8cfb_r.jpg
http://pic1.zhimg.com/v2-e76e0bf2985a3d5621e40e14550b1444_r.jpg
快速傅立叶变换：
http://pic2.zhimg.com/v2-e42964f6219d0ce5bdb1213535283ec1_r.jpg
分治法加速计算。
http://pic3.zhimg.com/v2-8abf99aff368840675762ca0deacd042_r.jpg
http://pic1.zhimg.com/v2-445dde4ef403a6baa61d48921f3f47ac_r.jpg
http://pic3.zhimg.com/v2-d2701f8e8f64c0d90f57a6bc9843dfd2_r.jpg
http://pic4.zhimg.com/v2-14fb9d3cf18d62e5dc6c6fbb49d9abc7_r.jpg
04、动态规划（变化多）
原理
http://pic2.zhimg.com/v2-33b0e9d36c8ff33a585ee2e7d3d5ac2d_r.jpg
http://pic1.zhimg.com/v2-b5927c263a775f527b105fad6a1652ac_r.jpg
http://pic1.zhimg.com/v2-43b8be7348ce91fb029463397b0e8fb0_r.jpg
http://pic2.zhimg.com/v2-86c003bcf6d881ebec472c3f1cfe6b01_r.jpg
例子：矩阵乘法 —— 计算量和计算顺序有关 —— 找最优的顺序
http://pic2.zhimg.com/v2-1c228e75d8e2655ed1f83d7a2a731a5d_r.jpg
http://pic4.zhimg.com/v2-62c15efeae4b6c1e2f7d1134fec0e9e3_r.jpg
http://pic4.zhimg.com/v2-bd9f0124f8b0209a1393402b4b12f97b_r.jpg
http://pic1.zhimg.com/v2-c21e210b404b8f16cf4e54fa976a9ea8_r.jpg
超大解空间是无法用枚举求出最优解。
http://pic1.zhimg.com/v2-4425ac3e248dc0d460f61251845dd3a4_r.jpg
http://pic3.zhimg.com/v2-1ae182b0a30efbe8af43ba06d99903f2_r.jpg
http://pic2.zhimg.com/v2-d9f4a0d4f72681df18c7dc21e6a9e28d_r.jpg
http://pic4.zhimg.com/v2-c4b98041b7ea2f23b8662d7f80c17897_r.jpg
http://pic2.zhimg.com/v2-facad579635ae21add2f6bc1ae2a0345_r.jpg
递归方程
[*]保存子问题优化解的数据结构 —— 数组
[*]计算顺序（填充顺序）
http://pic4.zhimg.com/v2-edd377bc3806e0e2f583d6d3ef5e8acf_r.jpg
http://pic3.zhimg.com/v2-2344520dfcf80ab4fad4a094324a9562_r.jpg
http://pic3.zhimg.com/v2-0c63590c05b8d55061b1917b0b350346_r.jpg
http://pic1.zhimg.com/v2-99e09309f21a74a0535080aced890740_r.jpg
http://pic2.zhimg.com/v2-d9ccd19c2b0431398d1670864177c0d9_b.jpg
http://pic1.zhimg.com/v2-1567acd106ca60019dc95f6aab642818_r.jpg
例子：最长公共子序列 ——
http://pic4.zhimg.com/v2-61a6772be7fce9fd9d62999da77ab423_r.jpg
http://pic3.zhimg.com/v2-3b3948ad72e7f981636d42d4b2e0004e_r.jpg
http://pic2.zhimg.com/v2-3dfb9be644859a2374364277ce9316a9_r.jpg
http://pic2.zhimg.com/v2-68dfc718524b1eaf5ebcde09ce3219a5_r.jpg
http://pic4.zhimg.com/v2-9442808622abfcc9465e2d81be83193f_r.jpg
http://pic1.zhimg.com/v2-4e476fdb56d8bf379579ba58fb897654_r.jpg
http://pic3.zhimg.com/v2-2dfbd177398f3bdd1fb10b186a99390a_r.jpg
http://pic1.zhimg.com/v2-5d9bbff9994a92ce16077b9d963158c8_r.jpg
http://pic4.zhimg.com/v2-589aa61572e8f10e0b5c0628500521a3_r.jpg
http://pic4.zhimg.com/v2-4697d62bfd3a7d5b14d65725c5842607_r.jpg
http://pic4.zhimg.com/v2-b74231acc57ca3ddf6f89377c995019b_r.jpg
http://pic3.zhimg.com/v2-cb6d6d3a568d6a437ab3b2c261a0f266_r.jpg
http://pic2.zhimg.com/v2-88842b0f0b6ea1fd5e81946a039cb70d_r.jpg
http://pic2.zhimg.com/v2-700849ddee7f582676b8ff382f238ff5_r.jpg
http://pic2.zhimg.com/v2-f50983746e4ae0d4fc035133e8a7a181_r.jpg
05、贪心法
基本原理
http://pic1.zhimg.com/v2-cc8bd198e6145ed4a43acd120880f014_r.jpg
http://pic4.zhimg.com/v2-e85126785d75d071a19c5d59c335de33_r.jpg
http://pic1.zhimg.com/v2-0ebaad7bf3c648ad3132490a9bb479d0_r.jpg
http://pic1.zhimg.com/v2-f5ea30eaa8873ee7bc750f33de8b20c8_r.jpg
http://pic2.zhimg.com/v2-fdbb07bc952d2e0ab60b2e8d5cd48eb9_r.jpg
任务安排问题
http://pic3.zhimg.com/v2-ac5cfc335e0614da2b03fb876261bd3a_r.jpg
http://pic2.zhimg.com/v2-cded2de08a9759306b63d6f73f9989a9_r.jpg
http://pic2.zhimg.com/v2-3be311f763cad959cd1c9e982fdcc5f5_r.jpg
http://pic3.zhimg.com/v2-20baae8a80728c2ff07ac13134bb864a_r.jpg
说明优化解结构
http://pic2.zhimg.com/v2-a63fd5e9c1285171cf4ee3376f9674bd_r.jpg
http://pic4.zhimg.com/v2-f1f55ea78d331048c835967336585f6f_r.jpg
http://pic1.zhimg.com/v2-54d246c6af4e9beea19cae829971cd4c_b.jpg
http://pic1.zhimg.com/v2-50d6ee4e9d170afd789959a1f13f50ac_r.jpg
Huffman编码：证明其正确性。
06、搜索策略
大部分事情都能做，但是可能弱一些。
暴力
布尔表达式的可满足性
http://pic3.zhimg.com/v2-a0951db0616ab1b954c5fa2aa1f5ec56_r.jpg
http://pic3.zhimg.com/v2-82d486bedd714b34ea36fea7a59db156_r.jpg
8-puzzle：
http://pic1.zhimg.com/v2-4e40612820237d5bc18eadf56dd0472c_r.jpg
http://pic3.zhimg.com/v2-742b18b2987bcee8b928c287a3a431c2_r.jpg
哈密顿环：
http://pic3.zhimg.com/v2-40c3c1d72e93bb7d14e7cb642ca94e46_r.jpg
http://pic1.zhimg.com/v2-83194382fde2e2c1244b3b93363ab3e4_r.jpg
http://pic3.zhimg.com/v2-11c60e3a01498bac5165076c23bafec6_r.jpg
BFS、DFS
http://pic3.zhimg.com/v2-44cecc5a92ef9a651110bf3eca13569a_r.jpg
http://pic2.zhimg.com/v2-d4bb52a386221a80ccb63e1e96643771_r.jpg
http://pic2.zhimg.com/v2-ee0155b73cac34b1cf868ec1c0ab4579_r.jpg
http://pic3.zhimg.com/v2-bc78a1c167bbd771c0af721282b3517a_r.jpg
http://pic3.zhimg.com/v2-2f1ebda6769e41ed74b4f8920a326a32_r.jpg
搜索的优化：爬山策略
http://pic3.zhimg.com/v2-e2bee0d178b05fe608afcb888d002502_r.jpg
启发式
http://pic1.zhimg.com/v2-a145bb812e51dce42e4f75e6bb1c4ea0_r.jpg
http://pic1.zhimg.com/v2-55c7fed4b193f595636ef87cbf648c9c_r.jpg
爬山法未必最优解。
Best-First搜索：全局观念
http://pic4.zhimg.com/v2-1d28be420a13b742488b35c3650b82c7_r.jpg
当前所有的节点中最好的。—— 堆
http://pic1.zhimg.com/v2-314822489f9c4275f0b60d426bd19178_r.jpg
http://pic4.zhimg.com/v2-20998029124b0e6cf92a108a3223b19f_r.jpg
分支界限：剪枝
http://pic3.zhimg.com/v2-77c2fc7e8f84b7d29a780bf771a76b3a_r.jpg
http://pic3.zhimg.com/v2-bb972f0cd682f7edd43adcc51fa7e6be_r.jpg
http://pic2.zhimg.com/v2-79a4c355449f0b909c3ad06bcb566e0d_r.jpg
http://pic2.zhimg.com/v2-ca7c11eb9e1cefdcdfeb2c1532c5b375_r.jpg
排除大于可能解的。
http://pic1.zhimg.com/v2-a66abc7f11337f394f4fe35ad866d6dc_r.jpg
07、字符串搜索
概述
http://pic4.zhimg.com/v2-65746b16ccbeadd4090d231c9ca03577_r.jpg
http://pic4.zhimg.com/v2-7f3e49485d1c90c695e8225672e4855f_r.jpg
http://pic4.zhimg.com/v2-c31c7aff48c2a0e04a4ede481171c53f_r.jpg
Rabin-Karp算法：指纹
http://pic1.zhimg.com/v2-449a932373f672c639ce74662c4e9554_r.jpg
http://pic3.zhimg.com/v2-b02d5908d57d6e657c0f13efc0390e02_r.jpg
http://pic4.zhimg.com/v2-cd1a971be26e635d41d853429446d5db_r.jpg
http://pic2.zhimg.com/v2-5f46e8295d1928a12ded91bcd51c8341_r.jpg
http://pic3.zhimg.com/v2-9b2c8229d1765b62e2b46ba166586d2e_r.jpg
http://pic3.zhimg.com/v2-cfa61685f23d8cc0b2f4385ea032feea_r.jpg
http://pic4.zhimg.com/v2-17266cd50c0e1e544755a3116188b867_r.jpg
KMP算法：最坏也是线性
http://pic1.zhimg.com/v2-8f45ee0d900024dc4ca7c98c7b9d57c0_r.jpg
BMH算法：
http://pic4.zhimg.com/v2-976723d709838aaa1b51a9d55f6c6e77_r.jpg
http://pic4.zhimg.com/v2-94a6c08dac5d00d0c72617df69ddc207_r.jpg
http://pic4.zhimg.com/v2-c5e42ae9c9109747395fb571fc0e4b87_r.jpg
http://pic4.zhimg.com/v2-1ba4bcf8126056d281abf1bb8fe3ab87_r.jpg
页:
[1]