我们更改编程语言时，时间复杂度会改变吗？ [英] Does time complexity changes as we change our programming language?

问题描述

在Python中，如果需要从列表中查找最大元素。我们使用：

 >>> max（listname）从列表中获取最大数目。 
时间复杂度：O（1）
  

如果我们使用C / C ++，则

 我们需要遍历循环并获得最大值。 
时间复杂度：O（n）或O（n平方）
  

因此，

解决方案

否。 max（listname）始终为O（N），其中 N 是 listname （*）。这只是根据复杂性的定义-因为迭代必须在某个地方进行-可能在您的代码中（对于C / C ++），或者在库代码中（对于Python）。

有时候我们忽略一些复杂性，通常是因为它不在我们的注意范围内；例如，Python中的 x * y （带有 x 和 y 是整数）实际上不是 O（1），因为 x 和 y 在Python中具有任意长度，因此 * 操作确实在循环中执行，但我们将其简化为O（1），如下所示：

通常情况下，整数的大小足够小而无所谓。

编程语言的选择仅重要，因为它会影响我们对什么的理解我们可以忽略；但实际上并不会改变时间复杂度。

---

*）如果<$ c，它只是O（N） $ c> N 与输入大小成正比；如果事先知道或受限制，则为O（1）。例如， lst = read_list（）; m = max（lst）是O（N），但 lst = [1,2,3,4]; m = max（lst）是O（1）， lst = read_list（）; lst = lst [：4]; m = max（lst）。

In Python, if we need to find the maximum element from the list. We use :

>>>max(listname) to get the maximum number from the list. 
Time Complexity : O(1)

If we use C/C++,

we need to iterate over the loop and get the max.
Time Complexity: O(n) or O(n square)

Hence, does the time complexity changes over the programming language?

解决方案

No. max(listname) is always O(N) where N is the length of listname (*). This is just by definition of complexity - because the iteration has to happen somewhere - maybe in your code (in case of your C/C++), or maybe in library code (in case of Python).

Sometimes we ignore some complexity, usually because it is beneath our notice; for example, x * y in Python (with x and y being integers) is actually not O(1), because x and y are of arbitrary length in Python, and the * operation thus does execute in loops, but we do simplify and treat it as O(1), as it is most often the case that the integers are of small enough size for it not to matter.

The choice of programming language only matters inasmuch as it affects our perception of what we can ignore; but it does not actually change the time complexity.

---

*) it is only O(N) in case N is proportional to input size; it is O(1) if it is known in advance, or limited. For example, lst = read_list(); m = max(lst) is O(N), but lst = [1, 2, 3, 4]; m = max(lst) is O(1), as is lst = read_list(); lst = lst[:4]; m = max(lst).

这篇关于我们更改编程语言时，时间复杂度会改变吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！