1

我不确定我是否正确地解决了这些问题，所以如果我错了，我需要有人告诉我。

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

这是 n-0 = n 分配，它是 O(g(n)) 对吗？

好的，知道了，如果我想获得这些问题中的作业数量和 O(g(n))：

 sum = 0;
 for ( i = 1 ; i < n * n ; j ++)
 {
    for ( j = 1 ; j <= n; j ++ )
    {
        sum += j;
    }
}

我所做的是， sum=0 是一个分配，外循环是 n^2 - 1 个分配，内循环是 n-1 个分配，最后总和是 1 个分配

因此，分配的数量是 2+(n^3+1) 这给出了 O(g(n^3))

在这个嵌套循环中：

 sum = 0;
 for ( i = 1 ; i <= n; i ++ )
 {
    for ( j = 1 ; j <= 100 ; j++) 
    {
        for ( k = 1 ; k <= n ; k ++ )
        {
            sum += k;
        }
    }
 }

我所做的是， sum = 0 是 1 个分配，然后第一个循环是 1-n 分配，第二个循环 99 最后一个循环 1-n，然后 sum = 2

所以我得到了 3+(1+n^2) 个作业，这给了我 O(g(n^2))

我刚才做的有什么问题吗？

4

1 回答 1

0

你的计算是正确的。唯一的可能是 - 有时它是 O(g(n^2)) 还是 O(g( 99 *n^2)) 很重要。乘数在大尺度 N 值上变得不那么重要，但在小尺度上 - 99 倍迭代的常数因子（当未由编译器优化时）可能很重要。

于 2013-09-24T22:09:31.353 回答