多项式时间 - 人们可以接受的时间复杂度(不会长到没尽头) P 问题 - 可以在多项式时间内解决的问题NP 问题 - 可以猜到答案,并可在多项式时间内验证是否正确的问题NPC(完全)问题 - 是 NP 问题,且其它所有 NP 问题都可约化到它的问题NP-Hard(难)问题 - 不一定是 NP 问题,但其它所有 NP 问题都可约化到它的问题时间复杂度的概念:给定算法的运行时间增长趋势,一般输入规模看成很大渐进)阶从低到高:1 < logn < n < nlogn < n2 < n3 < 2n < n! < nn「大 O 阶表示法」的计算原则:保留最高阶,去头去尾头:最高阶项的系数尾:非最高阶项与常数比如:6n3 + 4n2 + 10000 = O( n3 )10n2 + 2n = O( 2n)随机化算法分类 :数值随机化算法舍伍德算法拉斯维加斯算法蒙特卡罗算法棋盘覆盖(分治策略) :前提:棋盘必须正好有 2k× 2k( k = 自然数)个格子步骤:1、 将棋盘划分成 4 个子棋盘2、 除了有特殊格的子棋盘外, 其它 3 个盘里各取离结合点最近的格子, 组成骨牌3、 将每个子棋盘再划分成 4 个子棋盘,同样执行步骤 2。
4、 递归终止条件:子棋盘的普通格只剩 3 个比如一个 8× 8 的棋盘(书 p21 页例子):划为 4 等份:不看有特殊格那份,其它 3 份取离结合点最近的格子,拉黑,就形成了一块骨牌现在每份都有 1 块特殊格,然后每份再划 4 等份:每一小份重新执行上面的算法(递归了) ,忽视特殊份,拉黑离结合点近的然后继续递归,重复刚才的步骤(子问题结构完全相同) 当然这里棋盘比较小,到这里已经可以看出结果递归中止条件:当子棋盘(划出的小份)只剩下 3 个普通格时七种常用排序算法的时间复杂度:最好情况平均情况最坏情况稳定性O(?)O(?)O(?)冒泡nn2n2稳定选择n2n2n2稳定插入nn2n2稳定希尔n1.3nlog n ~ n2n2不稳定堆nlog nnlognnlogn不稳定归并nlog nnlognnlogn稳定快速nlog nnlognn2不稳定其中最坏情况最重要稳定性的意思:假设有一个数组 { 2, 5, 2, 7, 1 }其中第一个 2 假设叫 a 元素,第二个 2 叫 b 元素吧对其排序后得 { 1, 2, 2, 5, 7 }原本 a 在 b 前面,如果排序后, a 还在 b 前面,就是稳定的。
它们调换了就是不稳定的也就是说稳定性,决定了同值元素的顺序会不会变动理论上,希尔和堆排序不会考,因为上课没讲过0-1 背包(动态规划) :假设有 3 个物品:物品 A重 3斤,价值 4元;物品 A重 4斤,价值 5元;物品 A重 5斤,价值 6元考虑方式:当放了 n-1 个物品时,第 n 个物品放还是不放?设:C - 当前背包容量(斤)w[n] - 第 n 个物品的重量(斤)v[n] - 第 n 个物品的价值(元) F( n, C ) - 将前 n 个物品放入容量为 C 的背包时,能获取的总价值如果不放第 n 个物品:公式: F( n-1, C )如果放第 n 个物品公式: F( n-1, C - w[n] ) + v[n]简单来说, 就是把 C、w[n] 、v[n] 代入公式, 看 2 个公式哪个得出的结果大, 就选哪个然后可以构造出一张表:背包容量为C 时,能选择的最大价值重量价值C=1C=2C=3C=4C=5C=6C=7C=8C=9C=10A 3 斤4 元AXX44444444B4 斤5 元A + BXX45559999C5 斤6 元A+B+C XX45669101111解释下, X 表示放不下,因为这里最轻的物品也要 3 斤, C=1 或 2 时肯定放不下。
关键是后面绿色的值是怎么得到的,它是一行行构造出来的A 行表示只有物品 A 时,怎么放能得到最大价值A + B 行表示只有 A 与 B 时,怎么放能得到最大价值A + B + C行表示有 ABC时,怎么放能得到最大价值先看 A 行,因为就物品 A,也没有什么比较公式,很显然 C 大于 3 时就可以放进 A,因为每种物品就一个,所以不管背包多大,最大价值都是 4 元再看 A + B 行,从这行开始可以套公式了比如 C=3 时:F( n-1, C ): 就是 A 行 C=3 时的价值,也就是 4 元F( n-1, C - w[n] ) + v[n] : C-w[n] = 3 - 4 = -1 ,显然 4 斤的 B 根本放不进 3 斤的包所以最大价值是 4 元再比如 C=8 时,F( n-1, C ): 还是 4 元F( n-1, C-w[n] ) + v[n] : C-w[n] = 8 - 4 = 4, F( n-1, 4 ),也就是 A 行的 C=4,为 4,再加上 v[n]=5 ,最终结果是 9 元最大价值选大的, 9 元再看 A + B + C行,一样的,就举 C=9 时的例子吧:F( n-1, C ): A + B 放在 C=9,查表得 9 元。
F( n-1, C-w[n] ) + v[n] : F( A+B, 9-5 ) + 6 = 11元选大的, 11 元最终整表的右下角那个,就是整道题的最优解,即11 元所谓动态规划, 就是在算法中, 逐步建立起这张表填表过程中, 后面的值可能会依赖前面的值,这时只要去查表就行了,而不用去临时计算换言之,不做重复的子计算这种算法效率高了,但存表需要空间,典型的空间换时间的做法矩阵连乘(动态规划) :矩阵连乘怎么算不重要,这里不写了关键3点:1、 相乘的矩阵,前面一个的列数要与后面一个的行数相等比如 3 行5列与 5行 2列的可以乘而3行5列与 4行2列的没法乘2、 a 行 b 列与 b 行 c 列相乘,会得到一个3、 a 行 b 列与 b 行 c 列相乘,元素相乘次数a 行 c 列的矩阵 a× b× c(次)换言之,假设有不同的矩阵 A、 B、C那么( A×B)× C 与 A×( B×C),会产生不同的相乘次数而这个问题就是要找到,相乘次数最少的顺序举例来说,约定 A(3, 5)表示一个 3 行 5 列的矩阵, 假设有:A( 3, 5)B(5, 4)C( 4, 7)如果按(A× B)× C 的顺序:A×B = (3, 4),相乘次数 = 3×5×4 = 60( 3, 4 )× C,相乘次数 = 3× 4×7 = 84最终,整个连乘过程中,次数为 60+84 = 144(次)如果按 A×( B× C)的顺序:B× C = (5, 7),相乘次数A× ( 5, 7 )×C,相乘次数= 5×4×7 = 120= 3×5×7 = 105最终,整个连乘过程中,次数为 120+105 = 225(次)显然第一种乘得少,乘得少代表效率高,这就是我们追求的。
算法执行过程中,也会逐步建立2 张表(书上p48的( b)和(c)表)按书上的例子,有 6 个矩阵 A1~A6,最终填表得:断开位置表:A1A2A3A4A5A6A1011333A202333A30333A4045A505A6 0所谓断开位置,就是如何加括号(结合律)原式: A1× A2× A3× A4× A5× A6A1 到 A6 怎么断?查表为 3,也就是在 A3 左边断,得:( A1× A2× A3)×( A4× A5× A6)A1 到 A3 查表为 1,得:( A1×( A2× A3))×( A4× A5× A6)A4 到 A6 查表为 5,得:( A1×( A2× A3))×(( A4× A5)× A6)于是这就是答案,按这个顺序,元素相乘的次数最少相乘次数表:A1A2A3A4A5A6A1015750787593751187515125A2026254375712510500A3075025005375A4010003500A505000A60比如, A3 A4 A5 连乘,就查 A3~A5,得 2500,表示这 3 个矩阵连乘,最少元素相乘次数为 2500 次那么,我们最终要的答案当然就是 A1~A6,也就是 15125,6 个矩阵相乘最少 15125 次,这就是整体最优解。
动态规划法的常规步骤:1、 分析最优解的结构2、 建立递归关系3、 计算最优值4、 构造最优解单源最短路径(贪心) :用的迪杰斯特拉算法以书 p101 页的图为例:有 2 个集合:集合 S 放已启用的顶点,集合 U 放未启用的顶点具体看例子一开始集合 S = { A } ,只有起点A->BA->CA->DA->E最短路径A->B还到不了A->DA->E最短路径长度1030100所在集合UUUU查表可知, A 的邻点中,到 B 的距离最短,所以将 B 加入集合 SS={A,B}现在 A 可以到 C 了: A -> B -> C,填进去:A->BA->CA->DA->E最短路径A->BA->B->CA->DA->E最短路径长度106030100所在集合SUUU查表S={A,B,D}现在发现, A 到其它点的路径选择多了比如 A 到 E:A->E=100A->D->E=90显然后一条虽然经过的点多,但总路径短了,于是更新此表:(A 到其它点也是,只要有更短路径就换上去)A->BA->CA->DA->E最短路径A->BA->D->CA->DA->D->E最短路径长度10503090所在集合SUSU查表,在集合 U 中,选 A 过去最近的,发现是 A -> C = 50(路径 A -> D -> C)S={A,B,D,C}加入 C 后,继续找 A 到其它点有没有更短的走法,有的话就更新表A->BA->CA->DA->E最短路径A->BA->D->CA->DA->D->C->E最短路径长度10503060所在集合SSSU到此,集合 U 中只剩下 E,加入 S(路径 A -> D -> C -> E):S={A,B,D,C,E}最后次更新表( E 没有出去的方向,所以实际上本次无更新)A->BA->CA->DA->E最短路径A->BA->D->CA->DA->D->C->E最短路径长度10503060所在集合SSSS最终集合 U 中元素全部到了 S中,表则如上所示。
实际编程中,可以用一个数组表示此表,比如数组 arr , arr[2] 保存 A -> B 的最短路径长度, arr[3] 保存 A -> C的⋯⋯以此类推最终:arr[2] = 10arr[3] = 50arr[4] = 30arr[5] = 60那么,如果我现在想知道 A 到 C 怎么走最短,那么查表(数组)就可知:走路径 A -> D -> C最短,长度为 50可以看到,每次迭代,集合 U 都往集合 S 中送一个点而考虑上那个点并更新表后,每次都会获得当前最优的解当全部迭代完成,最终得到的表就是整体最优解表这一点要注意,贪心法解题,很多都只能获得近似解,但 迪杰斯特拉算法可以获得最优解 将以上步骤抽出来:1、 初始时,集合 S 只包含源点 o,集合 U 包含除了源点的其它顶点2、 从 U 中选取一个距离源点最短的顶点加入 S 中3、 以 S中现有顶点组成路径,审查 o 到其它点是否有更短路径,有则更新4、重复 2、3步最优装载(贪心) :比如有艘轮船,可以装 10 吨货物假设现在有 5 件货物,重量分别是 3、 1、 7、 4、9 吨装最多货物的思路:1、 先对货物按重量从小到大排序: 1、 3、 4、7、 9 吨。
2、 依次装船, 直到装不下 这里装上 1、3、4 后就放不了 7 了所以最多装 3 个简言之,先装轻的,再装重的,当然能装的就最多注意:虽然是贪心法,但 本题得到的一定是最优解 动态规划与贪心的关系:动态规划建表查表需花费时间、空间开销,效率比贪心低,但肯定能获得最优解贪心每次只取局部最优解,效率高,但整体不一定( 注意是不一定 )是最优解。