如何计算含子程序的函数渐近计算复杂度紧界？附实例求解

已知条件 #

子程序的渐近复杂度：

• a1(n) = O(n)
• a2(n) = O(n³)
• a3(n) = O(n log n)

函数c的复杂度分析 #

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

• 先分析if条件里的操作：
  • a2(n)*a3(n)的复杂度是两个子程序复杂度的乘积：O(n³) * O(n log n) = O(n⁴ log n)
  • a1(n)+a2(n)*a3(n)的复杂度由最高阶项主导，即O(n⁴ log n)
• 分支内的a1(n)复杂度为O(n)，远低于条件判断的复杂度，不影响整体上限
• 因此函数c的渐近紧界为O(n⁴ log n)

函数d的复杂度分析 #

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;
}

• 两层嵌套循环的总执行次数为n * n = n²次
• 每次循环调用a3(n)，复杂度为O(n log n)
• 总复杂度为循环次数乘以单次循环的复杂度：O(n²) * O(n log n) = O(n³ log n)

正确选项 #

对应选项 b) c = O(n⁴ log n) 且 d = O(n³ log n)

内容的提问来源于stack exchange，提问作者Fluellen