如何分析存在多种运行时间情况的算法时间复杂度？

当算法存在多种执行路径、对应不同运行时间函数时，不需要强行用单一函数概括，而是从最坏情况、最好情况、平均情况三个标准维度分别分析，这是复杂度分析里的常规做法：

1. 最坏情况分析（最常用） #

直接取所有可能执行路径中时间复杂度最高的结果，用来保证算法在任何输入场景下的时间上限。
以你给出的代码为例：

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

最坏情况是statement 1为True，此时时间复杂度为 Θ(n)（工程中也常用*O(n)*表示上界，更侧重最坏情况的时间限制）。绝大多数生产场景下优先关注最坏情况，因为要确保算法不会在极端输入下超时。

2. 最好情况分析 #

取所有路径中时间复杂度最低的结果，仅作为参考维度，不能代表算法的普遍表现。
比如你的代码中，statement 1为False时，时间复杂度为 Θ(1)。但最好情况往往是输入极端理想的场景，实际出现概率可能很低，单独参考它的意义有限。

3. 平均情况分析 #

如果能明确各分支的触发概率（比如statement 1为True的概率为p，且p由输入分布决定），可以计算加权平均后的时间复杂度：
平均时间 = p × Θ(n) + (1-p) × Θ(1)

• 若p是固定常数（比如50%概率触发循环），则平均复杂度仍为 Θ(n)；
• 若p随n趋近于0（比如大输入下几乎不会触发循环），则平均复杂度为 Θ(1)。
  不过平均情况需要依赖输入的概率分布，很多场景下无法精准定义，实际使用频率低于最坏情况。

另外补充：Big-O、Big-Ω、Big-Θ并非只能绑定单一函数——你可以用*O(n)表示算法的时间上界（最坏情况），用Ω(1)表示时间下界（最好情况），用Θ(n)或Θ(1)*分别对应特定分支的精确复杂度。

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