清华大学出版社 TSINGHUA UNIVERSITY PRESS 第2章递归与分治策略
第2章 递归与分治策略
清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法总体思想 ·对这k个子问题分别求解。如果子问题的规模仍然不够 小,则再划分为k个子问题,如此递归的进行下去,直 到问题规模足够小,很容易求出其解为止。 T(n) T(n/2) Tn/2) T(n/2) Tn/2)
• 将要求解的较大规模的问题分割成k个更小规模的子问 题。 算法总体思想 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = • 对这k个子问题分别求解。如果子问题的规模仍然不够 小，则再划分为k个子问题，如此递归的进行下去，直 到问题规模足够小，很容易求出其解为止
清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法总体思想 将求岀的小规模的问题的解合并为一个更大规模的问 题的解,自底向上逐步求出原来问题的解。 T(n) T424和2424)TAA4如2)T4(4厂(4)T白4(a4(a4Ja
算法总体思想 • 对这k个子问题分别求解。如果子问题的规模仍然不够 小，则再划分为k个子问题，如此递归的进行下去，直 到问题规模足够小，很容易求出其解为止。 n T(n) = n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) • 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解
清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法总体思想 将求岀的小规模的问题的解合并为一个更大规模的问 题的解,自底向上逐步求出原来问题的解。 T(n) T4J44J4)T4(44(A4)T44和44)T44r4ra
算法总体思想 • 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。 n T(n) = n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4)
清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法总体思想 将求岀的小规模的问题的解合并为一个更大规模的问 题的解,自底向上逐步求出原来问题的解。 分治法的设计思想是,将一个难以直接解决的大问题, 分割成一些规模较小的相同问题,以便各个击破, 分而治之。 凡治众如治寡,分数是也 孙小子兵法
算法总体思想 • 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。 n T(n) = n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) 分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。 凡治众如治寡，分数是也。 ----孙子兵法