了解这个问题的时间和 space 复杂性

Question

我有以下代码。有人告诉我，这个的时间复杂度是 O(n)。但我很难理解如何。对我来说好像是 O(n) + O(n) + O(n) = O(3n) 并且 space 复杂度也是 O(3n)，因为 3 个向量填充到 n 的大小。我的理解正确吗？

void productofself(std::vector<int> v)
{
    int multipliedProduct = 0;
    std::vector<int> left;
    std::vector<int> right(v.size());
    std::vector<int> result;
    for (int i = 0; i < v.size(); i++)
    {
        if (i == 0) 
        { 
            multipliedProduct = 1; 
        }
        else 
        {
            multipliedProduct *= v[i - 1];
        }
        left.push_back(multipliedProduct);
    }
   
    for (int i = v.size() - 1; i >= 0; i--)
    {
        if (i == v.size() - 1) 
        {
            multipliedProduct = 1;
        }
        else
        {
            multipliedProduct *= v[i + 1];
        }

        right[i]=multipliedProduct;
    }


    for (int i = 0; i < v.size(); i++)
    {
        result.push_back(left[i] * right[i]);
    }

}

Answer 1

我认为你忽略了渐近符号的要点。该代码是 O(3n) 但它也是 O(n) 并且后者才是最重要的。

O(3n) 和 O(n) 根据定义是等价的。

我们说 f(x) 是 O( g(x) ) 如果存在两个常数 m 和 k 使得 f(x) < m * g(x) 对于所有 x 大于k。基本上 f(x) 是 O(g(x)) 如果 x 足够大，f(x) 总是小于常数因子乘以 g(x).

因此您可以在该定义中看到常数因子：m。洗涤时会出现像 3 这样的比例因子。存在一个 m 使得 3 * n < m * n，即任何大于 3 的数。所以函数 f(n) = 3*n 是 O(n).

了解这个问题的时间和 space 复杂性

Understanding the time and space complexity of this problem

c++

time-complexity

space-complexity