这个算法有多复杂

Question

我真的很难理解大学的算法复杂性分析。我的教授给了我们一些简单的代码来计算复杂性，这就是其中之一：

double minValue(double* pd, int& p, int N)
{
    double minV = pd[0];
    for (int i=1; i < N; i++)
        if (minV > pd[i]) {
            minV = pd[i];
            p = i;
        }
    return minV;
}

有人能告诉我这有多复杂吗？我的猜测是 O(N²)

Answer 1

此函数唯一重复的部分是以下 for 循环：

for (int i+1; i < N; i++)

这个循环就是O(N)，所以这也是函数的整体复杂度。

Answer 2

由于函数的输入是一个数组、一个标量和一个标量，因此数组会影响您的时间复杂度。您只需要在 for 循环中遍历一次数组即可。增加输入的大小会线性增加 for 循环的时间，因为它将通过每个值一次。因此时间复杂度为 O(N).