Hom*_*me3 1 c++ algorithm boost time-complexity
我刚刚阅读了c ++中boost库的指南.我不明白累加器的部分.
在指南中它说每个累加器都可以拥有它的功能,例如tag :: min或tag :: mean.如果您拥有这些功能,则可以使用min函数(宏).
那么为什么我不能在STL中使用vector并使用像min_element(v.begin(),v.end())这样的算法？使用累加器有什么好处？
该指南还写了"累加器复杂度O(1)提取器复杂度O(1)".那是什么意思？它与时间复杂性有关吗？这是累加器的优势吗？
如果使用向量,则必须存储每个值.这需要内存,但是对于累加器的任务,实际上并不需要存储这些值 - 对于某些计算,只需要在给出新值时更新少量状态.
您可以编写一个节省空间的算法来执行计算,而无需使用所有存储,或者您可以使用已完成此工作的累加器.
此外,累加器库提供了标准库不具备的一些统计工具.
并且,是的,O(1)意味着"恒定时间复杂度",这告诉我们这种方法的另一个重要好处 - 随着数量变大,其性能不会变差.
| 归档时间： |
|
| 查看次数： |
138 次 |
| 最近记录： |