为什么O(2n ^ 2)和O(100 n ^ 2)在算法复杂度上与O(n ^ 2)相同？

Question

我是算法分析领域的新手.我在这里阅读Stack Overflow问题" 什么是"大O"符号的简单英语解释？ " O(2n^2)和O(100 n^2)那些相同O(n^2).我不明白这一点,因为如果我们采用n = 4,操作次数将为:

• O(2 n^2) = 32次操作
• O(100 n^2) = 1600次操作
• O(n^2) = 16次操作

任何人都可以解释为什么我们应该将这些不同的操作计数视为等效吗？

Answer 1

为什么这是真的可以直接从正式定义中得出.更具体地说,f(x) = O(g(n))当且仅当|f(x)| <= M|g(x)| for all x >= x0某些M和x0.在这里,您可以自由挑选M,如你所愿,所以如果M = 5对是真实的,那么你可以随便挑的是真的.f(x) = O(n2)M = 5*100f(x) = O(100 n2)

为什么这是有用的是一个不同的故事.

关于常量的一些问题很重要:

• 我们在测量什么操作？数组访问？算术运算？仅乘法？算术乘法加权加倍加法？并且您可能希望使用此度量标准来比较算法(具有相同的Big-O复杂度),而实际上即使是最有经验的计算机科学家也可能会错过的操作数量会有一些细微差别.
• 假设您可以为每个操作分配合理的权重.现在必须有一个全面的协议,否则你将对使用不同权重的人所做的算法进行一些近乎毫无意义的分析(除了大O会给你的信息).
• 权重可以是有时间限制的,因为操作速度随着时间而改善,并且一些操作可以比其他操作更快地改进.
• 权重可能受环境限制,因为操作速度可能因环境而异.例如,磁盘读取比读取内存要慢得多.

Big-O(渐近复杂度的一部分)避免了所有这些问题.您只需检查执行一段时间(即独立于输入大小)的某段代码的次数.例如:

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次加法,每次执行n 次³次,但这里我们只说这段代码:

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

在恒定时间内运行(无论数组中有多少元素,它总是需要相同的时间)并且将执行一次,因此运行时间为.O(n3)O(n3)