计算带有 for 循环条件的大 OH 表示法

Question

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

for (初始化、条件、增量(

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;
}

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

Answer 1

假设a = i需要 1 个时间单位，您可以考虑每个i：

• i = 0 ： n + 1
• i = 1 ： n
• i = 2 ： n - 1
• 。
• i = 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

与大哦符号的绳索，

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(