c++ - 多重线性运算会影响整体功能更坏情况的复杂性吗？

Question

这可能是一个有点简单的问题，但我还是要问各位:

我写了下面的函数:

std::vector<int> V={1,2,3,4,5};
int myFunction()
{
   for(int i=V.size();i--;){//Do Stuff};
   for int e=V.size();i--;){//Do Stuff};
}

这需要具有最坏情况下的时间复杂度 O(n) 和最坏情况下的空间复杂度 O(1)。

使用两个线性运算(for 循环)是否会将时间复杂度更改为 O(n) 以外的其他值？

Answer 1

没有。它不是。 O(N) 表示类似于 aN+b + 比线性 N 弱的东西。

甚至像这样的东西:T(N)= 5N+100 + Log(N) 也被认为是 O(N)。

“比线性 N 弱的东西”，我指的是满足方程的任何函数 R(N):

lim R(N)/N = 0 ; N-->Inifinity   //Use L'Hospital's Rule for solving these kind of limits

所以O(N)可以写成:

O(N) = aN+b + R(N)

---

旁注:复杂性不等于性能。虽然(N+N)仍然是O(N)，但这并不意味着它不比(N)慢。性能，就其最基本的形式而言，是关于你需要做某事的次数循环，而不是关于理论复杂性。

但是，至少当 N 达到非常大的数字(几乎无穷大)时，它应该是相关的。