"i*i" 不会使复杂度为 O(n^2) 吗？

Question

我在看一门关于 Big O 和算法复杂性的在线课程，对一个例子有疑问：

private static int func(long n) {

    int result = 0;

    for(int i = 0; i <= n; i++) {
        result = i*i;
    }

    return result;
}

讲师推导出它的复杂度是O(n)。我想，既然循环是 O(n) 但乘法是 O(n^2)，并且 i 取决于 n，它应该是O(n^2).

然后我写了一个示例 Java 应用程序来检查实际执行时间：

    private static long N1 = 10;
    private static long N2 = 100000;

    public static void main(String[] args) {

        long startTime1 = System.nanoTime();
        System.out.println(func(N1));
        long stopTime1 = System.nanoTime();
        long difference1 = stopTime1 - startTime1;

        long startTime2 = System.nanoTime();
        System.out.println(func(N2));
        long stopTime2 = System.nanoTime();
        long difference2 = stopTime2 - startTime2;

        System.out.println("N2 / N1 = " + N2 / N1);
        System.out.println("difference2 / difference1 = " + difference2 / difference1);
    }

结果是：

100
1410065408
N2 / N1 = 10000
difference2 / difference1 = 5

所以如果 N2 大 10^4 倍，执行时间就大 5 倍，即它是对数复杂度。这是为什么？是否可以在没有实际测试的情况下先验地推导出这个？

更新感谢大家，我发现我错过或误解了几件事。如果可以的话，我会接受每一个答案。谢谢大家！

Answer 1

先尝试重新运行您的测量值。不要计算打印出值所花费的时间，以消除一些不准确之处。

long startTime1 = System.nanoTime();
int res = func(N1);
res = func(N1);
...
res = func(N1);
long stopTime1 = System.nanoTime();
System.out.println(res);

其次你应该运行在测量时间的时候计算8次这样的时间，所以它运行s的时间更长，更能提高准确率。我更喜欢运行计算 30 秒或更长时间。并确保输入 n 足够大。即使这样运行整个测试至少三次并取平均结果。

编辑：RealSkeptic 关于热点预热的说法是正确的，他给出了 nice link 解释

下一个乘法可以运行在现代 CPU 的几个时钟周期内。从这个角度来看，乘法只是一个单一的操作。大 O 表示法可以让您专注于算法的一般速度感，因此您可以首先选择复杂度较低的算法。之后你可以做更多的代码和硬件特定的优化。

Answer 2

您可以通过找到最常见的指令（主导指令）或其中之一来计算时间复杂度。

在您的情况下，这是：i <= n 或仅执行 1 次的这些：result = i*i; 或 i++。虽然评估复杂性 -1 或 +1 并不重要，因此请选择您想要的任何一个。

然后您尝试通过 n 变量来制定显性指令的执行次数。在您的示例中，i<=n 恰好执行了 n+2 次，因此复杂度为 O(n+2) = O(n)，因为您在计算复杂度时不应该关心常量。

最后的注释： 乘法不是 O(n^2)，您可能将它与乘法 BigIntegers 混淆了，而不是普通的 ints.

Answer 3

复杂度为 O(n)，因为您的函数执行 n 个操作，无论您执行何种操作。

在这种情况下，当您将较大的 n 传递给 func 时，操作的数量将线性增长，这就是 O(n) 的复杂度。如果你有从 1 到 n 的嵌套循环，那就是 O(n^2)。

基准并不重要，因为它们是特定于实现的并且取决于其他因素。为了获得更准确的结果，将 func(N1) 和 func(N2) 的值保存到变量中，并在最后打印出这些变量。

Answer 4

大O是asymptotic时间，不是实际时间。我们不计算操作，我们显示输入数量与总体运行时间之间的关系。

虽然测量是正确的，但您还没有进行足够的测量以得出有用的结论。尝试 n 的数千个不同值，而不仅仅是两个，并绘制出您获得的运行次。在图中，您会发现异常值，但最终您会看到 n 和执行时间之间存在直线（线性）关系，因此为 O(n)。如果图形向上弯曲，则可能是 O(log n)、O(n log n)、O(n^2)、O(n!) 等

Answer 5

不，因为，

result = i*i;

尽管这可能需要很长时间，因为 i*i 可以对长数字进行非常大的位操作集。这被排除在外，因为这被视为单个机器指令，并且被认为需要一定的时间。请记住，时间复杂度并不能准确告诉您代码执行的时间。我们需要查看的只是告诉该指令执行多少次并将其映射到图形上的函数。它也不关心你的图表看起来像从原点或从 y=2 开始的线性图。它关心的是它是线性的。这就是为什么时间复杂度保持为 O(n) 的原因。

Answer 6

只是一个旁注：
即使 if 乘法在这里是相关的，重要的一点是如何执行乘法。对于原始类型，它是在硬件中实现的，因此我们可以将其视为常量O(1)。但即使忽略这一事实，CPU 也不会使用您在学校学到的纸笔方法实现乘法，而是使用 russian-peasant algorithm（又名古埃及乘法等），这将运行在 O(log max(n , m)) 中 n * m。

"i*i" 不会使复杂度为 O(n^2) 吗？

Doesn't "i*i" make the complexity O(n^2)?

java

time-complexity