为什么O（2N ^ 2）和O（100 N ^ 2）相同的算法复杂度为O（n ^ 2）？ [英] why O(2n^2) and O(100 n^2) same as O(n^2) in algorithm complexity?

问题描述

我是新的算法分析领域。我的堆栈溢出问题在这里阅读 该大O 的纯英文解释，啊， （2N ^ 2）和 O（100 N ^ 2）相同为O（n ^ 2）。我不明白这一点，因为如果我们取n = 4，操作的数量将是：

I am new in the algorithm analysis domain. I read here in the Stack Overflow question "Plain English explanation of Big O" that O(2n^2) and O(100 n^2) are the same as O(n^2). I don't understand this, because if we take n = 4, the number of operations will be:

• O（2 N ^ 2） = 32操作
• O（100 N ^ 2） = 1600的操作
• 为O（n ^ 2） = 16操作

• O(2 n^2) = 32 operations
• O(100 n^2) = 1600 operations
• O(n^2) = 16 operations

任何一个可以解释为什么我们应该把这些不同的操作数等同？

Can any one can explain why we are supposed to treat these different operation counts as equivalent?

推荐答案

为什么这是真的可以直接从的的正式定义。更具体地讲， F（X）= O（G（N））当且仅当 | F（X）| ＆LT; = M | G（X）|对于所有的x＆GT; = X 一些 M 和 X0 。在这里，你可以自由挑选 M 如你所愿，所以如果 M = 5 为 F（X）= O（N 2 ）是真实的，那么你可以随便挑 M = 5 * 100 为 F（X）= O（100 n的 2 ）是真实的。

Why this is true can be derived directly from the formal definition. More specifically, f(x) = O(g(n)) if and only if |f(x)| <= M|g(x)| for all x >= x0 for some M and x0. Here you're free to pick M as you wish, so if M = 5 for f(x) = O(n2) to be true, then you can just pick M = 5*100 for f(x) = O(100 n2) to be true.

为什么这是非常有用是一个有点不同的故事。

Why this is useful is a bit of a different story.

具有常量的关注关系：

• 什么操作，我们测量？数组访问？算术运算？乘法只？算术乘法加权双不亚于除？你可能要比较使用这个指标的算法（即具有相同大O的复杂性），而实际上有可能在操作，即使是最有经验的计算机科学家能够错过的数量有些细微的差别。
• 比方说，你可以指定一个合理的重量，以每个操作。现在，必须有全面协议，这一点，否则你就会有被别人使用不同的权重进行算法的一些近乎毫无意义的分析（不包括哪些信息大O会一直给你）。
• 的权重可以是有时间限制的，作为操作的速度随时间而改善，和某些操作可能提高快于其他
• 的权重可以是环境绑定，作为操作的速度可以不同在不同的环境中。例如，磁盘读取比内存读取慢很多。

大澳（这是渐进的复杂性部分）避免了所有这些问题。你只检查了多少次了一些片code，它需要的时间恒定量（即独立的输入大小）被执行。作为例子：

Big-O (which is part of asymptotic complexity) avoid all of these issues. You only check how many times some piece of code that takes a constant amount of time (i.e. independent of input size) is executed. As example:

c = 0
for i = 1 to n
for j = 1 to n
for k = 1 to n
  x = input[i]*input[j]
  y = input[j]*input[k]
  z = input[i]*input[k]
  c += (x-y)*z

因此​​，有4次乘法，1减1此外，每个执行ñ ³ 次，但在这里，我们只想说，这个code：

So there are 4 multiplications, 1 subtraction and 1 addition, each executed n³ times, but here we just say that this code:

  x = input[i]*input[j]
  y = input[j]*input[k]
  z = input[i]*input[k]
  c += (x-y)*z

在固定时间内运行（这将始终以相同的时间量，而不管有多少元素数组中），将执行为O（n 3 ）倍，因此运行时间为为O（n 3 ）。

runs in constant time (it will always take the same amount of time, regardless of how many elements there are in the array) and will be executed O(n3) times, thus the running time is O(n3).

这篇关于为什么O（2N ^ 2）和O（100 N ^ 2）相同的算法复杂度为O（n ^ 2）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！