7

According to my analysis, the running time of this algorithm should be N2, because each of the loops goes once through all the elements. I am not sure whether the presence of the if statement changes the time complexity?

for(int i=0; i<N; i++){
    for(int j=1; j<N; j++){

        System.out.println("Yayyyy");
        if(i<=j){
            System.out.println("Yayyy not");
        }
    }
}
4

6 回答 6

8
  • Tp：将常量文本打印到标准输出所需的时间。
  • Ti：内部循环内所有其他操作（谓词评估等）所花费的时间。
  • To：除执行内循环（初始化计数器等）外，外循环内所有操作所需的时间。
  • Tc：设置流程和其他所有簿记所需的时间

总运行时间将为Tc + N x (To + NxTi + N/2xTp)。

这等于Tc + NxTo + (Nx(N/2)) x (2Ti + Tp) ，当N趋于无穷大时， K > Ti + Tp/2的值以K x (N^2)为界。这个边界使得时间复杂度仍然是O(N^2)。

不，if语句不会更改此示例中的时间复杂度。

于 2012-09-01T21:46:21.110 回答
3

不。考虑到时间复杂度渐近地描述时间——我们将较低的时间复杂度吸收到较高的时间复杂度中。

O(n²)意味着k × n² + c假设它c是如此之低以至于我们不关心它。

这些是恒定的影响，整个事物（c）的一定数量的开销以及无论我们的复杂性是什么的一定数量的成本。如果一个算法有一个 lower ，或者如果它们相等，一个 lower ，它n²就会击败另一个算法。此外，对于足够低的 n 值，O(n²) 与 O(1) 相同（我们通常不会在意，但每个可能会有很大不同，而且如果我们每做一次 m 次，那么 O( n²m) 优于 O(m)，如果 n 很低，那不是真正比较的)..n²kck

无论如何，这是故意的过度简化，因为k并且c可能不是真的恒定，就像恒定一样好。因此，如果某件事是真的O(n² + log(n))，我们会称它为，因为当我们需要担心的时候O(n²)，谁会在乎这点小事呢？log(n)n²

所以。看着你的情况。我们做外循环，n次。对于其中的每一个，我们都会进行内部循环n-1时间。对于每个内部循环，我们进行第一次打印（成本的任何差异都与任何方式无关n，因此基本上是恒定的）和测试。测试成功的时间大约有一半，导致第二次打印的成本经常如此。

所以总成本为：

cost of setting up everything +
n × cost of looping + 
(n - 1) × cost of loop +
(n × (n - 1)) × cost of print +
(n × (n - 1)) × cost of test +
(n × (n - 1)) / 2 × cost of print.

为上面的常量赋值，我们得到：

k +
n × a +
(n - 1) × b +
(n × (n - 1)) × c +
(n × (n - 1)) × d +
(n × (n - 1)) / 2 × e.

=

k +
n × a +
(n - 1) × b +
(n × (n - 1)) × (c + d + (e / 2))

现在，因为c + d + e / 2它本身是常数，所以可以变成：

n × a + (n - 1) × b + (n × (n - 1)) × c + k

或重新排序，按最高顺序排列：

(n × (n - 1)) × c + (n - 1) × b + n × a + k

如果 n 高到足以让我们该死，那么 n 在比例上如此接近 n - 1，以至于我们不妨认为它们是相同的（时间复杂度的另一个方面是渐近地描述事物，即当 n 接近 ∞ 时，因此n² 和 (n × (n - 1)) 之间的差异接近 0)。因此：

n² × c + n × b + n × a = n² × c + n × (b + a) + k

同样， b + a 本身是常数，所以它等价于：

n² × k + n × c + a

现在我们做了前面提到的吸收较低时间订单的事情，谁在乎n × c，没关系？如果 n 高到足以让我们完全关心，那么一切都是关于 的n²。相比之下，我们不妨将总体开销的差异视为噪声，并将其视为：

n² × k + c

或者换句话说，如：

O(n²)

所以是的，你一开始就很努力，if 语句不会影响复杂性。

考虑到这一点，我们可以注意到时间复杂度有可能隐藏我们真正关心的内容。例如，如果我们有一个 O(n²) 算法，如果这种分析发现时间成本n² × k + n × c为 k 为 200µs，c 为 15s，那么在 n 大于 750000 之前，它实际上是每 n 位的成本，而不是每 n² 位。在较低的 n 处，它更接近我们对 O(n) 的期望，而不是 O(n²)。

时间复杂度有用的原因是，如此大的差异是罕见的，我们关心时间，因此关心时间复杂度，当 n 变高时（你可以隐藏一些可怕的 O(n!) 怪物在您在蓝月亮中调用一次的代码中，包含三个元素，只是不在乎）。因此，为了实现现实世界的改进，我们理想地希望降低时间复杂度，或者如果未能降低最高级别的常数 k（或者换句话说，如果你可以开始做 n log n 次而不是 n² 次，那么就做，否则减少你正在做 n² 次而不是你正在做 n 次的其他事情的成本）。

换句话说，它帮助我们专注于通常重要的事情。

于 2012-09-01T22:25:20.977 回答
0

简短的回答：运行时间仍然是 O(N^2)。

长答案：条件检查的成本可以安全地“添加”到 println 操作的权重中，就像您有两个 println() 而不是执行一个 println() 一样。（关于这个例子，请记住，像 println 这样的 I/O 操作的成本大大超过了简单的整数比较。）

也许您可以说 println() 调用花费“1 次操作”，而比较是“0.0001 次操作”，因此总成本将是“（1.0001 * N）^2 次操作，而不仅仅是 N^2。你已经还将 println() 的数量减少了一半，所以我们可以说你在 (1.0001 * N) ^ 2 / 2 次操作。这仍然是 O(N^2)，即使对于给定的值N 您可能通过仅打印一半条目将运行时间减半。

一般来说，比较的成本应该添加到由比较产生的分支内的操作成本中。当 if() {} 和 else {} 都存在时，测量运行时可能会更加困难。这里的一个策略是估计运行时间，就好像每次都发生最昂贵的操作一样；或者，如果单个分支的运行时间不是很容易知道的，则估计两个操作都在每次循环迭代中发生。如果这些操作都是 O(1)，那么你的运行时间的顺序仍然是 O(N^2)，因为你是线性缩放的。

于 2012-09-01T21:46:56.960 回答
0

No, the if doesn't affect the complexity.

于 2012-09-01T21:22:05.010 回答
0

The time complexity is the same, you will print Yayyyy N^2 times.

于 2012-09-01T21:22:13.730 回答
-1

of course, if you are working with comparison based algorithm, that s what u count right?

so in your case, you are looking at O(n2), because your if statement is being executed almost n2 times.

For non comparison algorithms you count whatever is your main operation.

于 2012-09-01T21:22:04.727 回答