这个方法的时间复杂度是常数吗?

问题描述 投票:0回答:2

我的任务是找出该方法的时间复杂度,但我不确定为什么它是恒定的。 我的想法是,总体时间复杂度是 n2^n,因为外循环运行 n 次,内循环运行 2^k 次,因为 k 每次都乘以两倍外循环运行。然而,当我使用

System.nanoTime()
测试该方法时,随着数据大小的增加,时间似乎保持不变。我不确定我是对还是错,但如果我错了,并且该方法具有恒定的时间复杂度,您能解释一下原因吗?谢谢!

public static void f6(int n) {
    int k = 1, a = 0;
    for(int i = 0; i < n; i += 1) {
        for(int j = 0; j <= k * 2; j += 1) {
            a = i + j;
        }
        k = k * 2;
    }
}

测试左栏:函数名;中间栏:项目数量;右栏:所用时间:

img1

java time-complexity
2个回答
0
投票

您将

a
k
变量定义为整数,并且(至少是
k
变量)不能增加到 ^2 超过 32 倍。因此 JVM 知道
k = k^2
的方程仅在前 31 次有意义,并且不会进行过多的迭代。

更重要的是,如果计算后不使用结果,JVM 也可以决定不执行计算。

所以,解决方案:

  1. int a,k
    更改为
    long a,k
  2. 使用结果(sysout 就足够了)

0
投票

我的想法是,总体时间复杂度为 n2^n,因为外循环运行 n 次,内循环运行 2^k 次,因为每次 k 都会乘以两倍。外循环运行。

嗯,O(n2n) 肯定是方法渐近复杂度的an上限。就目前而言,您的分析是正确的。但如果你看得更深一点,你可以得到一个更紧的,但仍然具有简单的形式。

写出一些内循环迭代计数:

1  2  4  8 ...

一直到 2n-1。所有这些的总和可以表示为 Σi = 1…n 2i-1。如果您还不知道这一总和的结果,那么您应该了解一下。我会让你这么做。

© www.soinside.com 2019 - 2024. All rights reserved.