相关疑难解决方法(0)

大多数拥有CS学位的人肯定会知道Big O代表什么.它可以帮助我们衡量算法的实际效率(如何),如果你知道你试图解决的问题属于哪个类别,你可以弄清楚是否仍然可以挤出那么少的额外性能.¹

但我很好奇,你如何计算或近似算法的复杂性？

¹ _{但正如他们所说,不要过度,过早优化是所有邪恶的根源,没有正当理由的优化也应该得到这个名称.}

在C ++ 11中，我使用它std::next是因为如果要更改vector为list，则不必更改其余代码。

对于list，std::next为O（n），因为我需要遍历所有元素。但是，这如何vector呢？我在cppreference上发现了这个注释：

但是，如果满足InputIt或ForwardIt额外满足LegacyRandomAccessIterator的要求，则复杂度是恒定的。

是否vector符合这些要求？以及为什么“传统”？