java “if”语句对时间复杂度分析有影响吗？

Do "if" statements affect in the time complexity analysis?

提问by FranXh

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

根据我的分析，这个算法的运行时间应该是 N ²，因为每个循环都会遍历所有元素。我不确定if语句的存在是否会改变时间复杂度？

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");
        }
    }
}

回答by Tugrul Ates

• Tp: time it takes to print a constant text to standard output.
• Ti: time it takes for all other operations inside the inner loop (predicate evaluation etc.).
• To: time it takes for all operations inside the outer loop except the execution of inner loop (initializing counters etc.).
• Tc: time it takes for setting up the process and every other bookkeeping

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

Total running time will be Tc + N x (To + NxTi + N/2xTp).

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

This is equal to Tc + NxTo + (Nx(N/2)) x (2Ti + Tp)which is bounded by K x (N^2)for values of K > Ti + Tp/2as Ngoes to infinity. This boundary makes the time complexity still O(N^2).

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

No, the ifstatement does not change the time complexity in this example.

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

回答by Jon Hanna

No. Consider that time-complexity describes time asymptotically - we absorb lower time-complexities into the higher.

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

O(n2)means k × n2 + cwhere it's assumed that cis so low that we don't care about it.

O(n2)意味着k × n2 + c假设它c太低以至于我们不关心它。

These are the constant effects, a certain amount of overhead on the whole thing (c) and a certain amount of cost per whatever our complexity is. One n2algorithm will beat another n2algorithm if it has a lower k, or if they're equal, a lower c. Also, O(n2) is the same as O(1) for sufficiently low values of n (and we normally won't care, but the kof each could be massively different, and also if we do each m times then while O(n2m) beats O(m), if n is low that's not what's really compared)..

这些是恒定的影响，对整个事物 (c) 的一定量的开销以及无论我们的复杂性是多少都会产生一定量的成本。一个n2算法将击败另一n2算法，如果它具有较低的k，或者如果他们是平等的，较低的c。此外，对于足够低的 n 值，O(n2) 与 O(1) 相同（我们通常不会关心，但k每个的 可能会有很大不同，而且如果我们每个都做 m 次，那么同时 O( n2m) 胜过 O(m)，如果 n 很低，那不是真正比较的）。

Anyway, this is a deliberate over-simplification, because kand cmight not really be constant, just as good as constant. Hence if something was really O(n2 + log(n)), we'd call it O(n2), because who cares about that little log(n)when we've an n2to worry about?

无论如何，这是一种故意的过度简化，因为k和c可能不是真正的常数，就像常数一样好。因此，如果某些事情是真的O(n2 + log(n))，我们会称它为O(n2)，因为log(n)当我们n2需要担心时，谁会在乎那一点呢？

So. Looking at your case. We do the outer loop, ntimes. For each of those, we do the inner loop n-1times. For each of those inner loops we do the first print (any variance in cost is not related to nin any way, so essentially constant) and the test. The test succeeds roughly half the time, resulting in the cost of the second print that often.

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

So the total cost is:

所以总成本是：

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.

Assigning values to the constants above, we get:

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

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))

Now, since c + d + e / 2is itself constant, that can become:

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

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

Or to re-order, in order of highest order first:

或者重新排序，先按最高顺序：

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

If n is high enough for us to give a damn, then n is proportionally so close to n - 1 that we might as well consider them the same (another aspect of time complexity describing things asymptotically, that is as n approaches ∞ and hence the difference between n2 and (n × (n - 1)) approaches 0). Hence:

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

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

Again, b + a is itself constant, so it's equivalent to:

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

n2 × k + n × c + a

And now we do what was mentioned earlier of absorbing lower time orders, who cares about n × c, never mind a? If n is high enough for us to care at all, then it's all about n2. In comparison, we might as just consider the difference to the overall overheads as noise and treat it as:

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

n2 × k + c

Or in other words, as:

或者换句话说，如：

O(n2)

So yes, you were bang on it to begin with, and the if statement doesn't affect the complexity.

所以，是的，您一开始就很成功，并且 if 语句不会影响复杂性。

Considering this, we can note that it's possible for time complexity to hide what we really care about. If for example, we had a O(n2) algorithm were this sort of analysis found a time cost of n2 × k + n × cwere k amounted to 200μs and c amounted to 15s, then until n is greater than 750000 it's actually the per-n bit that costs, rather than the per-n2 bit. At lower n it's closer to what we'd expect from O(n) than from O(n2).

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

The reason time-complexity is useful, is a combination of so large a disparity being rare, and that we care about time, and hence about time-complexity, more when n gets higher (you could hide some horrible O(n!) monstrosity in your code that you call once in a blue moon, with three elements and just not care). Hence to bring about real-world improvements we ideally want to reduce the time complexity, or failing that reduce the highest level constant k (or in other words, if you can start doing things n log n times instead of n2 times then do, otherwise reduce the cost of that thing you're doing n2 times rather than something else you're doing n times).

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

In other words, it helps us focus on what normally mattres.

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

回答by lyngvi

Short answer: Runtime is still O(N^2).

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

Long answer: The cost of the conditional check can safely be "added" to the weight of the println operation, the same as if instead of doing one println(), you had two println()'s. (Regarding the example, bear in mind that the cost of I/O operations like println vastly outweigh simple integer comparisons.)

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

Perhaps you could say that the println() call costs "1 operation", and the comparison is "0.0001 operation", so the total cost would be "(1.0001 * N)^2 operations instead of just N^2. You've also cut the number of println()'s in half, so we can say you're at (1.0001 * N) ^ 2 / 2 operations. This is still O(N^2), even though that for a given value of N you may have halved the runtime by only printing half the entries.

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

In general, the cost of the comparison should be added to the cost of the operations within the branch(es) resulting from that comparison. When both if() {} and else {} are present, it can be more difficult to measure runtime. A tactic here is to estimate runtime as if the most expensive operation occurs every time; or, if the runtime of a single branch is not readily knowable, estimate as though bothoperations occur with every loop iteration. If those operations are both O(1), the order of your runtime remains O(N^2) since you're scaling linearly.

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

回答by DarthVader

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(n²), because your if statement is being executed almost n²times.

所以在您的情况下，您正在查看 O(n ²)，因为您的 if 语句几乎被执行了 n ²次。

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

对于非比较算法，您计算主要操作。

回答by VoidStar

No, the if doesn't affect the complexity.

不，如果不影响复杂性。

回答by Per Alexandersson

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

时间复杂度是一样的，你会打印 Yayyyy N^2 次。