algorithm - 依赖循环的复杂性

Question

2我开发了一种算法，我试图以最详细的方式记录它的时间复杂度，但我遇到了一个问题。

算法看起来像这样:

for i=0:n {
    task 1;
    task 2;
    for j=0:i {
        task 3;
    }
    task 4;
}

所以我通过说任务 1 的复杂度为 O(t1) 来记录我的复杂度，...但是当我试图解释任务 3 时，我被卡住了，因为它基本上会被执行 i 次，我打算说 lagorithm 的复杂度是任务 1 + 任务 2 + i * 任务 3 + 任务的复杂度的 n 倍4. 因为我会依赖 n 我真的不知道什么是呈现事物的最佳方式。

我知道如果任务 1、2 和 4 不存在，复杂度将为 O(n^2)。但我不知道如何与我之前的解释保持一致。

我希望这是有道理的，谢谢你的帮助。

Answer 1

最简单的方法可能是分别计算。

任务 3 被执行:1+2+3+...+n = n(n+1)/2次。

任务 1、2 和 4 各执行 n 次。

所以(假设每个任务花费 O(1))我们的复杂度为

O(n(n+1)/2 + 3n) = O(n²/2 + n/2 + 3n) = O(n²)

(在大 O 表示法中可以忽略常数因子和渐近较小的项)。

---

更一般地(如果每个任务不一定需要O(1))我们可以说复杂度是:

O(t3*n² + n*(t1 + t2 + t4))

其中 ti 表示任务 i 需要多长时间。