求以下'for'循环的计算复杂度

Question

下面for循环的复杂度是多少？

n = 0;
for (i = 1; i <= N; i++)
{    
    s(i) = sum of the first i coordinates of a
           fixed vector (of dimension N);

    % suppose r(i) (for all i) is already computed
    if (r(i) s(i) > r(n) s(n))
        n = i;  
}

Answer 1

循环的最坏情况复杂度为 o(N²)。

循环执行了N次。每次迭代都对 N 有另一个依赖，因为：

s(i) = sum of the first i coordinates of a fixed vector (of dimension N);

我在这里看不到 N 的任何依赖关系，所以在 http://en.wikipedia.org/wiki/Big_O_notation 中它只是常量：

% suppose r(i) (for all i) is already computed
if (r(i) s(i) > r(n) s(n))
    n = i;