求助：含f(n)、g(n)的嵌套循环算法时间复杂度分析

首先明确前提：

• 调用函数f(n)的时间复杂度：上界O(logn)，下界Ω(1)
• 调用函数g(n)的时间复杂度：上界O(n)，下界Ω(log₂n)
• 需分别分析最坏情况和最好情况的时间复杂度，同时要注意if (f(n)+g(n) > n²)的触发条件是否成立，这取决于f(n)和g(n)的返回值范围（用户标注存在歧义，需分两种场景讨论）

场景1：标注的是函数的时间复杂度（返回值无限制） #

这种情况下，f(n)和g(n)的返回值可以足够大，使得f(n)+g(n) > n²成立。

最坏情况（O(n² logn)） #

外层循环执行n次，且每次都触发内层循环：

1. 每次外层循环中，第4行调用f(n)（O(logn)）和g(n)（O(n)），总开销为O(n)（n是高阶项）
2. 内层循环执行O(logn)次，每次迭代调用2次f(n)和2次g(n)，单次迭代开销为O(n)，内层循环总开销O(n logn)
3. 单次外层循环总开销为O(n) + O(n logn) = O(n logn)，n次循环后总复杂度为O(n × n logn) = O(n² logn)

最好情况（Ω(n logn)） #

外层循环执行n次，且从不触发内层循环：

1. 每次外层循环中，第4行调用f(n)（Ω(1)）和g(n)（Ω(logn)），总开销为Ω(logn)
2. n次循环后总复杂度为Ω(n logn)

场景2：标注的是函数返回值的渐近范围 #

这种情况下，f(n) = O(logn)（即f(n) ≤ C logn），g(n) = O(n)（即g(n) ≤ Dn），当n足够大时，f(n)+g(n) ≤ C logn + Dn < n²，因此if条件永远不会触发。

最坏情况（O(n²)） #

每次外层循环调用g(n)取时间上界O(n)，调用f(n)取时间上界O(logn)，单次循环开销O(n)，n次循环后总复杂度O(n × n) = O(n²)

最好情况（Ω(n logn)） #

每次外层循环调用g(n)取时间下界Ω(logn)，调用f(n)取时间下界Ω(1)，单次循环开销Ω(logn)，n次循环后总复杂度Ω(n logn)

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