算法时间复杂度计算：函数调用乘积的复杂度分析

给定代码 #

int F1(int n, int s) {
    for(int i=0; i<n; i++) s++;
    return n;
}

int F3(int n, int s) {
    for(int i=1; i<n; i*=2) s++;
    return s;
}

问题描述 #

需要计算表达式 F1(n,0) * F1(F1(n,0) * F3(n,0),0) 的时间复杂度。

本人已完成的分析：

• F1(n,0)*F3(n,0) 的结果为 n*log₂(n)，对应的执行复杂度为 O(n) + O(log₂(n))；
• F1(n*log₂(n),0) 的执行复杂度为 O(nlogn)，第一个F1(n,0)调用的复杂度为 O(n)。

存在以下疑问：

1. 最终复杂度是 O(n) + O(nlogn) = O(nlogn)，还是 O(n)*O(nlogn) = O(n²logn)？
2. 若表达式中间为 + 号，时间复杂度会有变化吗？

解答 #

疑问1解答 #

时间复杂度的核心是累加所有执行步骤的总耗时，而非对各函数的复杂度做乘法。该表达式的完整执行流程耗时如下：

• 调用第一个F1(n,0)：耗时O(n)；
• 计算内部参数时，调用F1(n,0)：耗时O(n)；
• 调用F3(n,0)：耗时O(logn)；
• 计算乘积n*logn：常数时间O(1)；
• 调用F1(n*logn, 0)：耗时O(nlogn)；
• 最终执行乘法运算：常数时间O(1)。

将所有步骤的耗时累加后得到：O(n) + O(n) + O(logn) + O(nlogn)，忽略低阶项后最终复杂度为O(nlogn)。你提到的O(n)*O(nlogn)是错误思路——乘法是函数返回值的运算，和时间复杂度的计算无关。

疑问2解答 #

如果表达式改为F1(n,0) + F1(F1(n,0) * F3(n,0),0)，所有函数调用的执行流程和耗时都没有变化，仅最后一步将乘法替换为加法（依然是常数时间）。因此总时间复杂度仍然是O(nlogn)，没有变化。

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