如何计算具有子程序的函数的渐近计算复杂度的紧界？

Question

我面临着这个与计算复杂性和大O表示法相关的问题。我很难理解子例程如何影响函数的总体复杂性。我是否将复杂度最高的子例程视为函数的上紧界，或者我是否必须计算某种组合复杂度？问题是这样的：

“函数 c 和 d 调用子例程 a1、a2 和 a4，其计算复杂度如下：

a1 = O(n)，a2 = O(n³) 且 a3 = O(n log n)。

void c(int n) {
        int z = 0;
        if (a1(n)+a2(n)*a3(n) > 1)
            z = 1 + a1(n);
       return z;
    }
    
void d(int n) {
        int i, j, s = 0;
        for (i=0; i<n; i++)
            for (j=0; j<n; j++)
                s = s + a3(n);
        return s;
    }

为函数 c 和 d 的渐近计算复杂度选择紧界。

a) c = O(n⁶ log n) 且 d = O(n²)

b) c = O(n⁴ log n) 且 d = O(n³ log n)

c) c = O(n³) 且 d = O(n³ log n)

d) c = O(n⁴) 且 d = O(n³ log n)

e) c = O(n³) 且 d = O(n² log n)

f) c = O(n⁴ log n) 且 d = O(n²)"

提前感谢您的帮助！

Answer 1

首先，请注意

void c(int n) {
    int z = 0;
    if (a1(n)+a2(n)*a3(n) > 1)
        z = 1 + a1(n);
    return z;
}

没有循环。要评估该函数，您必须对

a1

、

a2

和

a3

分别评估一次，并可能再次评估

a1

。由于您基本上对每个函数进行一次评估，因此函数的时间复杂度归结为性能最差的子例程的时间复杂度，

a2

，即 O(n^3)。

在时

void d(int n) {
    int i, j, s = 0;
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            s = s + a3(n);
    return s;
}

你有一个循环，它将迭代 O(n^2) 次，并且在每次迭代中你调用一个需要 O(n log n) 时间的函数。因此，我们将时间复杂度相乘，得到 O(n^3 log n)（因为我们要做的事情需要 O(n log n) 秒，也就是说，O(n^2) 次）。