代码的O()， θ()和Ω()时间复杂度

Question

请帮我查一下以下代码的O(), θ(), Ω()时间复杂度

if(x<A) Func1(n);
else if(x<A+1000) Func2(n);
else if(x<A+5000) Func3(n);
else Func4(n);

给定

:

Func1(n)=θ(n)
Func2(n)=θ(2^n)
Func3(n)=θ(logn)
Func4(n)=O(n)
Func4(n)=Ω(logn)

Answer 1

设f为显示代码定义的函数，设f₁...f₄为Func1...4。如果没有关于x和A的信息，那么关于f，我们最多可以得出的结论是，f(n)的下界是适用于f₁...f₄的最小下界，上界是适用于f₁...f₄的最大上界。它们的最小下界为Ω(n)，最大上界为O(2n)，因此f(n)的复杂度为Ω(n)和O(2n)。

问题(如最初所述)中f₄(n)的复杂性没有定义，因为一个函数的下界为n log n的倍数，其上界不能为n的倍数。然而，给定的f₄边界O(n)和Ω(nlogn)都不在Ω(n)和O(2n)的范围之内。

Edit:修改后的题目，f₃为θ(logn)， f₄为Ω(log n)， O(n)。f₁...f₄现在的最小下界是Ω(log n)，而f(n)的复杂度是Ω(log n)和O(2n)。如果没有x和A的信息，则不存在函数g(n)，使得常数C₁和C₂存在，且C₁·g(n) < f(n) < C₂·g(n)渐近，因此f()不存在θ()界。