0

我被本周的课堂作业困住了，这是我真正想学习的主题，所以有一次我想我会做额外的阅读！！！！

该方法是为我们提供的，我只是编写一些测试用例。这是我的知识变得有点模糊的地方。如果时间增加，那么我低估了我认为的复杂性？在这种情况下，n^3 不够，n^4 太多，因此逐渐减少到 0。

这意味着在 2 之间存在一个复杂性，这就是 log n 出现的地方，因为 log n 是一个小于 n 的值？但据我所知，这是

我真的希望有人能用比讲座幻灯片上的解释更好的解释为我消除这种困惑，因为它们对我毫无意义，谢谢

/**
 * Number 5
 */
public int Five(int n)
{
    int sum=0; 
    for(int i=0; i<n; i++){
        for(int j=0; j<i*i; j++){
            sum++;
        }
    }

    return sum;
}

   public void runFive()
    {
// Test n^2 complexity 
//         System.out.println("We are passing the value 5, This returns us an n value of " + Five(5) + " , With a time complexity of " + complexityN2(Five(5), 5) + " This is to test the value of 5 in a n^2 test" );
//         System.out.println("We are passing the value 10, This returns us an n value of " + Five(10) + " , With a time complexity of " + complexityN2(Five(10), 10) + "This is to test the value of 10 in a n^2 test" );
//         System.out.println("We are passing the value 100, This returns us an n value of " + Five(100) + " , With a time complexity of " + complexityN2(Five(100), 100) + "This is to test the value of 100 in a n^2 test" );
//         System.out.println("We are passing the value 1000, This returns us an n value of " + Five(1000) + " , With a time complexity of " + complexityN2(Five(1000), 1000) + "This is to test the value of 1000 in a n^2 test" );
//         System.out.println("We are passing the value 10000, This returns us an n value of " + Five(10000) + " , With a time complexity of " + complexityN2(Five(10000), 10000) + "This is to test the value of 10000 in a n^2 test" );

// Test n^3 complexity          
//         System.out.println("We are passing the value 5, This returns us an n value of " + Five(5) + " , With a time complexity of " + complexityN3(Five(5), 5) + " This is to test the value of 5 in a n^3 test" );
//         System.out.println("We are passing the value 10, This returns us an n value of " + Five(10) + " , With a time complexity of " + complexityN3(Five(10), 10) + "This is to test the value of 10 in a n^3 test" );
//         System.out.println("We are passing the value 100, This returns us an n value of " + Five(100) + " , With a time complexity of " + complexityN3(Five(100), 100) + "This is to test the value of 100 in a n^3 test" );
//         System.out.println("We are passing the value 1000, This returns us an n value of " + Five(1000) + " , With a time complexity of " + complexityN3(Five(1000), 1000) + "This is to test the value of 1000 in a n^3 test" );
//         System.out.println("We are passing the value 10000, This returns us an n value of " + Five(10000) + " , With a time complexity of " + complexityN3(Five(10000), 10000) + "This is to test the value of 10000 in a n^3 test" );
//         

//Test n^4 complexity
        System.out.println("We are passing the value 5, This returns us an n value of " + Five(5) + " , With a time complexity of " + complexityN4(Five(5), 5) + " This is to test the value of 5 in a n^3 test" );
        System.out.println("We are passing the value 10, This returns us an n value of " + Five(10) + " , With a time complexity of " + complexityN4(Five(10), 10) + "This is to test the value of 10 in a n^3 test" );
        System.out.println("We are passing the value 100, This returns us an n value of " + Five(100) + " , With a time complexity of " + complexityN4(Five(100), 100) + "This is to test the value of 100 in a n^3 test" );
        System.out.println("We are passing the value 1000, This returns us an n value of " + Five(1000) + " , With a time complexity of " + complexityN4(Five(1000), 1000) + "This is to test the value of 1000 in a n^3 test" );
        System.out.println("We are passing the value 10000, This returns us an n value of " + Five(10000) + " , With a time complexity of " + complexityN4(Five(10000), 10000) + "This is to test the value of 10000 in a n^3 test" );

    }

以下是复杂性方法

public double complexityN2(double time, double n)
{
    return time / (n * n);
}

public double complexityN3(double time, double n)
{
    return time / (n * n * n);
}

 public double complexityN4(double time, double n)
{
    return time / (n * n * n * n);
}

public double complexityLog(double time, double n)
{
    return time / (Math.log(n) * (n*n));
}
4

5 回答 5

5

请记住，大 O 表示法描述了当项目数接近无穷大时的行为。因此，在处理几乎任何实际计算量时，您不应该期望看到精确匹配。事实上，在任何情况下，您都不一定会看到精确匹配——它可能会渐近地接近匹配，但即使（从实际角度）所涉及的数字非常大，它仍然不是非常紧密的匹配。对于您在部分测试中使用的少量数字（例如，5、10、100），即使在最好的情况下，拟合通常也会非常差。

从时间的角度来看，Java 的大多数实现也使生活变得更加困难。问题是大多数 JVM 将解释某些代码的前几次（其中“少数”定义相当松散）迭代，然后才决定它的执行频率足以值得编译成更优化的机器代码。您使用的数字几乎肯定足够小，以至于在某些情况下，您正在计时解释代码和其他编译代码（并且在那里的某个地方，执行包括编译代码所花费的时间）。这对大 O 表示法的准确性没有实际影响，但是（尤其是对于小数字）可以并且将会对您的时间与大 O 预测的拟合程度产生重大影响。

于 2009-10-18T14:31:50.317 回答
4

在这种情况下 n^3 是不够的

这不是真的。外部循环Five恰好运行 n 次。对于 i 的每个值，内部循环恰好运行 i² 次，因此外部循环执行的步数是 i² 的总和，而 i 从 0 运行到 n-1，即 n/6 - n²/2 + n³/ 3（用归纳法简单证明）。这是一个三次多项式，因此它是 O(n³)。

于 2009-10-18T14:51:01.543 回答
4

您问题中唯一的问号出现在这句话的末尾：

这意味着在 2 之间存在一个复杂性，这就是 log n 出现的地方，因为 log n 是一个小于 n 的值？

那句话不是一个问题，而是一个陈述：你在这里问什么？

如果您要问是什么log(n)，那么它是p当 10（表示为 log 10）或e（在谈论自然对数时）提高到该幂（即 10 p，e p）时产生的数字n。因此，随着 n 的增加，它的上升非常缓慢（实际上与指数增加正好相反）：

log 10 (10) 是 1 (10 1 == 10)
log 10 (100) 是 2 (10 2 == 100)
log 10 (1000) 是 3 (10 3 == 1000)

抱歉，如果您已经知道这一切。

于 2009-10-18T14:03:47.373 回答
3

恐怕您没有正确解决问题：盲目地测试功能只会让您到目前为止。

O() 表示法实际上就像是说，对于一个非常大的 x 值，函数在时间 (aO(x)) 中完成，其中 a 是任意常数（可以是 0.00001 以及 6305789932）。

我们来看代码：内循环执行了2次，而（外循环）执行了n次，i从0到n。

现在，执行内部操作 (sum++) Sum i=1,n i 2，根据维基百科的智慧，它变为 (*)：

然后是应用 O() 表示法的时候了。对于较大的 n（例如 10 100），n 3压倒 n 2甚至更多 n 1，因此您只需丢弃它们：O(*) = O(n 3 )，这是练习的解决方案。

高温高压

于 2009-10-18T14:55:05.420 回答
0

试着像这样理解它——我们需要找到循环执行的次数来找到时间复杂度。这里的总和也代表相同的数字，这就是为什么您可以在复杂性函数中使用它来代替时间。这个假设是基于这样一个假设，即一个语句的每个处理都需要一个恒定的时间。如果我们计算循环运行的次数 - for i = 0 内部循环运行 0 次 for i = 1 内部循环运行 1 次 for i = 2 内部循环运行 4 次 for i = 3 内部循环运行 9次所以对于 i = m 内部循环运行 m*m 次

所以处理的语句总数可以计算为 -- sum = 0 + 1 + 4 + 9 + .... + m m + ... +(n-1) (n-1) sum = 1 + 4 + 9 + .... + m m + ... +(n-1) (n-1) 这些是自然数的平方 前 N 个自然数的和可以找到 - N(N+1)(2N +1) / 6 在我们的例子中 N=n-1 所以 sum = (n-1)(n)(2n-1) / 6 sum = (nn -n) (2n -1) /6 sum = (2n. nn - 2n.n - nn -n) /6 sum = (2n^3 -3n^2 -n) / 6 sum = 1/3n^3 - 1/2n^2 -1/6n

现在，Big O 只会考虑 n 的最高阶。所以你的复杂度是 n^3 的阶

现在，您的 n^3 时间复杂度函数将采用这个数字并将其除以 n^3，因此您的总和将类似于 1/3 - 1/2n^-1 -1/6n^-2。

对于 n^4 ，一个更小的数字，随着 n 的增加会变得更小，这解释了逐渐减少到 0。

于 2009-10-18T15:01:49.340 回答