比较Python中的根查找算法
我想在Python中比较几种寻找函数根的方法，比如牛顿法或者其他一些简单的计算方法。我觉得写这些算法应该不会太难。
那么，比较这些方法的好办法是什么呢？我稍微了解了一下大O符号。这样做合适吗？
7 个回答
大O符号是用来描述算法在极限情况下的表现，也就是当n变得非常大的时候。这种理论上的研究比实际实验要简单得多。我建议选择一些容易测量的内容，比如准确性和消耗的计算资源（时间/内存），这些都是人们关心的。
当你写程序来比较两个算法时，其实是在进行一项科学实验，就像有人在测量光速，或者比较吸烟者和非吸烟者的死亡率，很多因素都是相似的。
尽量选择一个能代表性的问题，或者至少是你感兴趣的问题来解决，因为你的结果可能不适用于你没有实际测试的情况。如果你从一个大问题集合中随机抽样，发现所有随机样本的表现都差不多，或者至少趋势相似，那么你可能能扩大结果适用的范围。即使理论研究表明应该有一个不错的n log n趋势，你也可能会得到意想不到的结果，因为理论研究通常不会考虑缓存突然用完、内存不足，或者整数溢出等情况。
要注意错误来源，并尽量减少这些错误，或者让它们对你比较的所有内容影响相同。当然，你希望对所有测试的算法使用完全相同的输入数据。对每个算法进行多次运行，检查结果的变化情况——可能有几次运行比较慢，因为那时计算机在做其他事情。要知道，缓存可能会让算法的后续运行变得更快，特别是当你紧接着运行它们的时候。你想要测量的时间取决于你决定要测量什么。如果有大量的输入输出操作，记得现代操作系统和计算机会在内存中缓存大量的磁盘I/O。我曾经在每次运行后都把电脑关掉再开，只有这样才能确保设备的I/O缓存被清空。
大O符号主要用来描述算法在输入量“增加”时的表现。这种方式可能不太适合用来衡量求根算法的效果。
我觉得，衡量求根算法的一个更好标准是需要多少次迭代才能把实际误差降到某个很小的值（我们称之为ε）。另一个标准是需要多少次迭代才能让连续两次迭代的结果差异小于这个ε。（如果你手头没有准确的根值，使用连续迭代的差异作为标准可能更合适。在实际操作中，你会用这种连续差异来判断什么时候停止求根算法，所以在这里也可以用这个标准。）
虽然你可以通过不同算法之间的迭代次数比例来描述它们（比如一个算法可能需要大约十倍的迭代次数才能达到和另一个算法相同的精度），但通常情况下，随着输入的变化，迭代次数并不会“增长”。
当然，如果你的算法在处理“更大”的输入时需要更多的迭代次数，那么使用大O符号就有意义了。
@sarnold的回答是对的——做大O分析没有意义。
根查找算法之间的主要区别有：
- 收敛速度（需要多少次迭代才能找到结果）
- 每次迭代的计算量（每次计算需要花费多少时间和资源）
- 输入要求（比如，你是否需要知道函数的导数，或者在二分法中是否需要设置上下限等）
- 适用的函数类型（比如，对多项式函数效果很好，但对有极点的函数就不行）
- 对函数的假设（比如，假设函数的导数是连续的，或者是解析的等）
- 方法的实现难易程度（这个方法有多简单，容易上手吗）
我觉得你会发现，每种方法都有一些优点和缺点，并且在某些情况下是最合适的选择。