计算算法复杂度-混淆 [英] Computing Algorithm Complexity - Confusion

问题描述

我有以下代码段:

sum = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < i; j++)
        sum++;

复杂度为 O(n ^ 2)，但是如果我想进一步挖掘内部循环的复杂度，则为(n(n-1))/2 或(n-1)！?

The complexity would be O(n^2), but if I want to dig a little more for the internal loop complexity then would it be (n (n-1))/2 or (n-1)!?

推荐答案

是，O(n ^ 2)，但实际上是0 + 1 + ... + n-1 = n(n-1)/2 = O(n ^ 2)，绝对不是(n-1)！

Yes, O(n^2), but actually 0+1+...+n-1=n(n-1)/2 = O(n^2), definitely not (n-1)!

这篇关于计算算法复杂度-混淆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！