algorithm - 在循环 block 中包含循环的 else block 的复杂性

Question

我试图找到每个语句的频率和这个方法的大 o。

但我正在为 else 部分苦苦挣扎，我知道我们采用了 if 和 else 的最糟糕的复杂性

但从逻辑上讲，在这种情况下，我是否已将外循环 (n) 的频率乘以 else 循环 (n+1) 的频率？虽然我知道 else block 只会执行一次，当 i=0 时 但是当我们遵守规则时，我们必须乘以它 所以我被困在这里，我不知道在这种情况下该怎么办，我希望你们能帮助我 谢谢!

int i, j, sum = 0;
for (i = 0 ; i < n; i++)
if ( i != 0)
    Sum += i;
else
    for (j = 0 ; j< n; j++)
        Sum + = j;

Answer 1

所以，你有一个 O(n) 的循环和一个 O(n) 的循环。 但是在您的代码中，我们只执行一次 else 语句。

所以你有一个 for 循环，在 if 中你做 O(1) 工作 (n - 1) 次，并且一次 (i == 0) 你做 O(n) 工作(当到达 else 语句时)

所以复杂度为 O(n) = (n - 1) * O(1) + O(n) ~ O(2n) 这也是 O(n) 因为我们在进行渐近分析时删除了常量。