O 表示法帮助

Question

我被这周的课堂作业困住了，这是我真的很想学习的一个主题，所以这一次我想我应该做额外的阅读！

该方法已为我们提供，我只是编写一些测试用例。这是我的知识变得有点模糊的地方。如果时间增加，那么我低估了我相信的复杂性？在这种情况下，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));
}

Answer 1

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

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

Answer 2

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

这意味着 2 之间有一个复杂性，这就是 log n 的用武之地，因为 log n 是一个小于 n 的值？

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

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

log₁₀(10) is 1 (10¹ == 10 )
log₁₀(100) 为 2 (10² == 100)
log₁₀(1000) is 3 (10³ == 1000)

如果您已经知道这一切，我们深表歉意。

Answer 3

在这种情况下 n^3 不够

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

Answer 4

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

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

我们看一下代码：内循环执行了i²次，而(外循环)执行了n次，i从0到n。

现在，执行内部运算（sum++）Sum_i=1,ni²，
根据维基百科的智慧，它变成 (*):

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

华泰

Answer 5

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

因此处理的语句总数可以为 --
总和 = 0 + 1 + 4 + 9 + .... + mm + ... +(n-1)(n-1)
总和 = 1 + 4 + 9 + .... + mm + ... +(n-1)(n-1)
这些是自然数的平方
前 N 个自然数的和可以计算为 - N(N+1)(2N+1) / 6
在我们的例子中 N=n-1
所以总和 = (n-1)(n)(2n-1) / 6
总和 = (nn -n) (2n -1) /6
总和 = (2n.nn - 2n.n - nn -n) /6
总和 = (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。