所有栏目

比较“分治法”和“动态规划法”的异同点和优缺点

已输入 0 字
优质回答
  • 共同点: 将待求解的问题分解成若干子问题,先求解子问题,然后再从这些子问题的解得到原问题的解。不同点:

    1、适合于用动态规划法求解的问题,分解得到的各子问题往往不是相互独立的; 而分治法中子问题相互独立。

    2、动态规划法用表保存已求解过的子问题的解,再次碰到同样的子问题时不必重新求解,而只需查询答案,故可获得多项式级时间复杂度,效率较高; 而分治法中对于每次出现的子问题均求解,导致同样的子问题被反复求解,故产生指数增长的时间复杂度,效率较低。

    2023-10-24 17:39:26
  • 共同点:将待求解的问题分解成若干子问题,先求解子问题,然后再从这些子问题的解得到原问题的解。不同点:

    1、适合于用动态规划法求解的问题,分解得到的各子问题往往不是相互独立的;而分治法中子问题相互独立。

    2、动态规划法用表保存已求解过的子问题的解,再次碰到同样的子问题时不必重新求解,而只需查询答案,故可获得多项式级时间复杂度,效率较高;而分治法中对于每次出现的子问题均求解,导致同样的子问题被反复求解,故产生指数增长的时间复杂度,效率较低。

    2023-10-24 17:39:26
最新问题 全部问题