1)列出分治法适用条件 2）请详细说明分治法解决该题的算法复杂度

1) 分治法适用条件：

- 问题可以被分解为多个子问题，这些子问题可以独立地解决。
- 子问题的结构和原问题相同。
- 子问题之间是相互独立的，即一个子问题的解不会影响另一个子问题的解。
- 可以将子问题的解合并成原问题的解。

2) 分治法解决问题的算法复杂度：

- 分解问题：将原问题分解成若干个规模较小且结构与原问题相似的子问题。
- 解决问题：递归地解决每个子问题。当子问题足够小并且可以被解决时，停止递归。
- 合并问题：将所有子问题的解合并成原问题的解。

对于一个规模为n的问题，如果每次分解成k个子问题，每个子问题的规模为n/k，那么该问题的递归树深度为logk(n)，每层的计算复杂度为O(n)，所以总的计算复杂度为O(nlogk(n))。

以归并排序为例，每次将数组分成两个长度为n/2的子数组，需要递归地对两个子数组进行排序，然后将两个有序的子数组合并成一个有序的数组。分解问题的时间复杂度为O(1)，解决问题的时间复杂度为O(nlogn)，合并问题的时间复杂度为O(n)，所以总的时间复杂度为O(nlogn)。