《算法分析与设计-动态规划和分治递归》由会员分享,可在线阅读,更多相关《算法分析与设计-动态规划和分治递归(8页珍藏版)》请在金锄头文库上搜索。
算法复杂度回溯法 排列 :n皇后,旅行商 n!子集 背包 2,迷宫 2,m着色 m贪心算法 Kruskal 宗教问题,活动安排 nlogn动态规划 矩阵连乘 n最长公共子序列 mnprim 最小生成树 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顺序不同乘的次序会有不同分治法递归法