IF 如何影响复杂性? [英] how does IF affect complexity?

问题描述

假设我们有一个包含 1.000.000 个元素的数组，我们遍历所有元素以检查一些简单的东西，例如第一个字符是否为A".根据我(很少)的理解，复杂度将是 O(n) 并且需要一些 X 时间.如果我添加另一个 IF(不是 else if)来检查，比方说，如果最后一个字符是G"，它会如何改变复杂性?它会使复杂性和时间加倍吗?像 O(2n) 和 2X?

Let's say we have an array of 1.000.000 elements and we go through all of them to check something simple, for example if the first character is "A". From my (very little) understanding, the complexity will be O(n) and it will take some X amount of time. If I add another IF (not else if) to check, let's say, if the last character is "G", how will it change complexity? Will it double the complexity and time? Like O(2n) and 2X?

我想避免考虑不同命令必须进行的计算数量.例如，我知道与简单的字符比较相比，Len() 需要更多的计算才能为我们提供结果，但是假设 IF 中使用的命令将具有(几乎)相同的复杂度.

I would like to avoid taking into consideration the number of calculations different commands have to make. For example, I understand that Len() requires more calculations to give us the result than a simple char comparison does, but let's say that the commands used in the IFs will have (almost) the same amount of complexity.

推荐答案

O(2n) = O(n).概括来说，O(kn) = O(n)，k 是一个常数.当然，使用两个 IF 可能需要两倍的时间，但执行时间仍然是输入大小的线性函数.

O(2n) = O(n). Generalizing, O(kn) = O(n), with k being a constant. Sure, with two IFs it might take twice the time, but execution time will still be a linear function of input size.

编辑:这里 是对不太面向数学的大 O 符号的解释，并附有示例

Edit: Here is an explanation, with examples, of the big-O notation which is not too mathematic-oriented

这篇关于IF 如何影响复杂性?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！