范围变化时的复杂性是多少？

Question

如果你有这样的算法，复杂度是多少：

int get(const std::vector<unsigned int>& v, int N)
{
    int a = 0;
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < v.size(); ++j)
            for(int k = 0; k < v[j]; ++k)
                a += k * v[j];
    return a;
}

除了缺少有用性之外，如果一个因素的变化如此之大，您认为复杂性是什么？我的意思是，当 V = v.size() 时肯定是 O(N * V * ?)，但那又如何呢？

Answer 1

复杂度为

O(N * V * std::numeric_limits<unsigned int>::max()) = O(N * V)

因为std::numeric_limits<unsigned int>::max()是一个常数。

Answer 2

取决于V[j] if v[j]=1, 则复杂度为O(N*V) if V[j]=N 则复杂度为O(N², V).

Answer 3

O(Nv.size() max(v)) ---> [O(N*v.size()*int.Max)]. 请注意您的代码可能是错误的，因为您没有收到任何异常 [try v[0] = int.Max]

Answer 4

此算法的复杂度未知。它类似于以下内容：

void foo(int arg) {
   int i = random() - arg;
   for (j = 0; j<i; ++j) 
        do_stuff();

无法评估此 foo() 的复杂性。

范围变化时的复杂性是多少？

What's the Complexity when range varies?

c++

complexity-theory

time-complexity