sul*_*4bh 9 algorithm analysis
在分析算法的有效性时,我有兴趣了解除空间和时间之外的参数.例如,我们可以在开发加密算法时专注于有效的陷阱功能.您还能想到其他什么？
首先,这是正确的.无论输入是什么,请确保您的算法始终有效.即使对于算法未设计处理的输入,您也应该打印错误消息,而不是使整个应用程序崩溃.如果您使用贪心算法,请确保它们在每种情况下都能正常工作,而不仅仅是您手动尝试的几种情况.
那就是实用的效率.在实践中,O(N 2)算法可以比O(N)算法快得多.做实际测试并且不要太依赖理论结果.
然后很容易实现.您通常不需要最佳的介绍排序实现来对100个整数的数组进行一次排序,所以不要打扰.
查找算法中的最坏情况,如果可能,请尽量避免使用它们.如果您的算法通常较快,但最糟糕的情况非常糟糕,请考虑检测最坏情况并使用另一种算法解决它,该算法通常较慢,但对于这种情况更好.
考虑空间和时间的权衡.如果你能负担得起内存以获得更好的速度,那么可能没有理由不去做,特别是如果你真的需要速度的话.如果你买不起记忆,但可以放慢速度,那就去做吧.
如果可以,请使用现有库.如果您可以使用GMP,请不要滚动自己的多精度库.对于C++来说,诸如boost,甚至STL容器和算法之类的东西已经被一大群人所使用了很多年,而且很可能比单独使用它更好.
稳定性(排序) - 算法是否保持相等元素的相对顺序？
数值稳定性 - 当使用非常大或小的实数时算法是否容易出错？
正确性 - 算法是否始终给出正确的答案？如果没有,误差幅度是多少？
一般性 - 算法在许多情况下是否有效(例如,有许多不同的数据类型)？
紧凑性 - 算法程序是否简洁？
并行化 - 当并发执行线程数增加时,性能如何扩展？
缓存意识 - 算法是否旨在最大限度地利用计算机的缓存？
缓存遗忘 - 算法是针对特定的缓存大小/缓存行大小进行调整,还是与缓存的参数无关地运行良好？
复杂.2个算法在所有其他方面都是相同的,更简单的算法将成为未来定制和使用的更好的候选者.
易于并行化.根据您的使用情况,它可能没有任何区别,或者另一方面,使算法无用,因为它不能使用10000个核心.