在循环块中包含循环的 else 块的复杂性

Question

我正在尝试找出每个语句的出现频率以及此方法的关键所在。

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

但从逻辑上讲，在这种情况下，我是否已将外循环 (n) 的频率乘以 else 循环 (n+1) 的频率？虽然我知道 else 块只会执行一次，当 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) 因为我们在做渐近时去掉了常量分析。