高中好友突然问我一道这样的问题，似乎是因为他们专业要做一个计算器，其中的一道习题是要求计算器实现这样的功能。
整理一下要求：解aX + e^X = b 方程。解方程精度要求0.01，给定方程只有一解，a>0,b>0,0<X<20。
当被第一次问及这样一个问题的时候，我脑海里反映的第一个方法就是「牛顿迭代法（NewtonMethod」。然而自己算法功底太差了，从来没有真正去了解过牛顿迭代法，反正早晚都是要学的，正好便借着这个机会学习了一个。
我一直认为牛顿迭代法的效率应该是几个近似求解方程的最快方法，于是查了一下百度百科后进行了实现。
实现代码如下：
#include<stdio.h>
#include<math.h>
#define MAX 20
#define MIN 0
#define MID 10
#define eps 1e-2
#define fx a*x+exp(x)-b
#define fdx a + exp(x)
double a,b,x;
double binary() ; // 二分查找
double NewtonMethod() ; // 牛顿迭代法
int main()
{
scanf("%lf%lf",&a,&b);
printf("%.2lf\n",binary()) ;
printf("%.2lf\n",NewtonMethod()) ;
return ;
} double binary() // 二分查找
{
x = MID ;
double x1 =MIN , x2 = MAX ;
while( fabs(fx) > eps)
{
if( fx < )
x1 = x ;
if( fx > )
x2 = x ;
x = ( x1 + x2) / ;
}
return x ;
} double NewtonMethod() // 牛顿迭代
{
x = ;
while()
{
if( fabs(fx) > eps )
{
x = x - (fx) / (fdx);
}
else return x ;
}
}
网上普遍都是牛顿迭代法求解一元二次方程或者平方根，我于是照猫画虎根据牛顿迭代法的核心x1=x0 - f(x) / f'(x) 照猫画虎学习了一个。关于证明还不是太会，自己手画了一下发现这样的方法近似非常快，我记得曾今刚看到过资料说两次迭代好像eps就可以小于多少……
自己代码功底还是太差了，二分也写跪多次，写出了什么if (fx < 0 ) x = ( x + MAX ) / 2这样现在看来有点羞耻想笑的代码。最后遇到最大的一个问题是在牛顿迭代法 fx / fdx 因为fx和fdx是用宏定义的，直接展开后导致运算优先级出现了问题然后各种程序跑崩……所以这里宏定义以后要考虑加括号，要认真考虑优先级问题，不然出了问题感觉挺难发现的。
以前前辈们总说代码要多写多练多手敲，就算把书上代码照抄到电脑上都是很好的。一直不能理解，觉得这样做没什么意义。现在深刻感觉到，代码看再多遍不如自己手写一遍，算法理论知道再清楚，不多手写几次就不知道坑在哪里，就实现不出来。以后一定多写代码。
不过最后有一个问题我一直不能理解：
为了比较其与二分的效率，我写了一个随机器准备对拍一下：
#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std ;
int main()
{
srand((int) time() ) ;
freopen("a.out","w"
,stdout) ;
for( int x = ; x <= ; x++)
cout << rand() % + <<' ' << rand() % + <<endl ;
return ;
}
产生了一万组 1 - 20 的数据文件，然后重定向到文件分别跑了一下数据，利用<ctime>下的 (double ) clock() / CLOCK_PER_SEC 来计算时间。
测试结果如下：
一万组数据 牛顿迭代反而慢于二分，不知道是因为我的数据产生中没有考虑过有方程有没有解的情况，还是程序写的不好或者输入输出有问题……？
不太会分析两个这样的算法的时间复杂度，真诚询问。二分法我感觉应该是O(nlgn) ?不会证明牛顿迭代法……就更难分析牛顿迭代法了……理论上我感觉牛顿迭代法的性能应该优于二分法啊。不知道问题出在哪里了……