《算法分析与设计-动态规划和分治递归》由会员分享，可在线阅读，更多相关《算法分析与设计-动态规划和分治递归（8页珍藏版）》请在金锄头文库上搜索。
算法复杂度 回溯法 排列 ：n 皇后，旅行商 n！ 子集 背包 2， 迷宫 2， m 着色 m 贪心算法 Kruskal 宗教问题,活动安排 nlogn 动态规划 矩阵连乘 n 最长公共子序列 mn prim 最小生成树 n 分治法 二路并归 nlogn矩阵连乘当 i=j 时，Ai:j=Ai，因此，mii=0，i=1,2,n当 ij 时，若 Ai:j的最优次序在 Ak和 Ak+1之间断开，i=kj,则：mij=mik+mk+1j+pi-1pkpj。由于在计算是并不知道断开点 k 的位置，所以 k 还未定。不过 k 的位置只有 j-i 个可能。因此，k 是这 j-i 个位置使计算量达到最小的那个位置。综上，有递推关系如下：总计算次数=Ai:k+Ak+1:j+Ak*Ak+1顺序不同乘的次序会有不同分治法递归法
