使用 for 循环条件计算大 oh 符号

Question

我试图理解函数的 Big-oh 表示法的计算，当函数包含一个 for 循环时，它具有特定的条件

for (initialization, condition, increment)

or() 如下所示：

    public void functE( int n ) 
    {
       int a;
       for ( int i = 0; i < n; i++ )
           for ( int j = 0; j <= n - i; j++ )
               a = i;
    }

我想这个函数的大 O 是 O(n^2)，这有效吗？

Answer 1

假设a = i占用1个时间单位，可以考虑每个i:

我 = 0 : n + 1
我 = 1 : n
我 = 2 : n - 1
...
我 = n - 1 : 2

总计：

T(n) = (n+1) + (n) + (n-1) + ... + 2 = n + [1 + ... + n] = n + n * (n + 1)/2 = (n^2 + 3n) / 2 = O(n^2)

Answer 2

使用表格法，复杂度为n^2+(2-i)n+2

根据 Big-Oh 表示法，

let f(n)=n^2+(2-i)n+2
f(n) <= c*g(n)
n^2+(2-i)n+2 <= n^2+(2-i)n+(2-i)n
n^2+(2-i)n+2 <= n^2+2(2-i)n
n^2+(2-i)n+2 <= n^2+n^2
n^2+(2-i)n+2 <= 2n^2

因此，c=2 且 g(n)=n^2， f(n)=O(g(n)) = O(n^2)

使用 for 循环条件计算大 oh 符号

calculate big oh notation with for loop condition

algorithm

time-complexity

big-o

analysis