Question

最大子段和问题中,分治法和动态规划法的时间复杂度分别是多少?分治法分为哪三

Answer 1

最大子段和问题中,分治法和动态规划法的时间复杂度分别是，治法分为哪三具体如下：

分治法顾名思义，就是“分而治之”，把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。动态规划是将复杂的问题分解为相对简单的相似子问题求解。

它是用来解决最优化问题的，难点在于怎样定义问题（状态），并且要保证定义的问题满足最优子结构性质和无后效性。治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服。

被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题。

直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)。