请问c++中二分法和分治算法有什么区别吗？

Question

c++中二分法和分治算法有什么区别吗？

Answer 1

二分与分治的区别是：

1. 对于区间[a，b]上连续不断且f（a）·f（b）<0的函数y=f（x），通过不断地把函数f（x）的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法。分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。

2. 二分法的算法是：

   （1）确定区间[a,b],验证f(a)·f(b)<0,给定精确度ξ.

   （2）求区间(a,b)的中点c.

   （3）计算f(c).

   01若f(c)=0,则c就是函数的零点;

   02若f(a)·f(c)<0,则令b=c;

   03若f(c)·f(b)<0,则令a=c.

   04判断是否达到精确度ξ:即若|a-b|<ξ,则得到零点近似值a(或b),否则重复2-4.

   分治法的算法是：Divide-and-Conquer(P)

   （1）if |P|≤n0

   （2）then return(ADHOC(P))

   （3）将P分解为较小的子问题 P1 ,P2 ,...,Pk

   （4）for i←1 to k

   （5）do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi

   （6） T ← MERGE(y1,y2,...,yk) △ 合并子问题

   （7） return(T)

   
   

Answer 2

有，但不大，就是内存的区别