如何分析不同运行时间的算法的时间复杂度

Question

我对算法的时间复杂度感到困惑，因为算法的运行时间是由 n, f(n) 的函数表示的。

例如：f(n) = 3n^2 + 5n + 1 = θ(n^2)

但是如果一个算法有多个f(n)，例如：

if statement 1 then
    for i = 1 to n do
        statement 2
        statement 3
        ...

如果语句 1 为 True，则 f(n) = n * 常数 = θ(n) 如果语句 1 为 False，则 f(n) = 常量 = θ(1) 如何确定具有多个 f(n) 的算法的运行时间？

我不知道如何分析它，因为 big-oh big-omega 和 big-theta 都是基于单个函数 f(n)。

Answer 1

对于这样的事情，你仍然可以表达最坏情况或最好情况的时间复杂度。为了更好地了解算法如何在现实世界数据上执行，您可能还想找到平均情况时间复杂度