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

问题描述

假设我们有一个1.000.000元素的数组，我们通过所有这些元素检查一些简单的东西，例如，如果第一个字符是A。根据我的（非常小的）理解，复杂性将是 O（n），并且需要一些X时间。如果我添加另一个IF（不是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?

I我们希望避免考虑不同命令必须进行的计算次数。例如，我理解Len（）需要更多的计算才能给出结果而不是简单的char比较，但是我们可以说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.

编辑：< a href =http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html>这里是一个大O的例子的解释不太过于数学化的符号

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

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