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

Question

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

for (initialization, condition, increment)

或()如下:

    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
• i = 1 : n
• i = 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)