关于从开始到结束并通过向量返回的复杂性

Question

我试图熟悉算法的复杂性评估.一般来说,我认为这是一种优秀/优雅的做法,但具体而言,我需要它来表达我的C++代码的时间复杂性.

我有一个小疑问.假设我有一个算法只从头到尾读取数据 std::vector; 那么它从结束到开始都是一样的(索引"从0到N"后跟"从N到0")也是2个循环.

• 我对自己说,这个东西的复杂性是O(2N):这是正确的吗？
• 一旦我到达开头,假设我想从头到尾再次开始读取所有数据(总共传递3次向量):是复杂度O(3N)？

这可能是一个愚蠢的怀疑,但我想对我的思考过程有任何意见.

Answer 1

Big-O表示法仅表示:

f(n)= O(g(n))当且仅当f(n)/ g(n)在n增加时不会增长到无穷大

你要做的是计算你正在执行的操作数,即f(n),然后找到一个至少与f一样快的函数g(n).

在你走一条路然后再回来的例子中,操作次数是f(n)= 2n因为每个元素被读取两次,所以,你可以选择g(n)= n.由于f(n)/ g(n)= 2n/n = 2显然不会增长到无穷大(它是常数),因此你有一个O(n)算法.

它当然也是一个O(2n)算法:因为当你将g(n)乘以常数时,"增长到无穷大"属性不会改变,任何O(g(n))也是定义为O(C任何常数C的g(n))算法.

它也是一个O(n²)算法,因为2n/n²= 2/n向零减小.Big-O表示法仅提供复杂性的上限.