代码之家 › 专栏 › 技术社区 › Laurence Wingo

用大O符号表示常量意味着什么?

big-o

Laurence Wingo · 技术社区 · 6 年前

我在看一段关于“大O”符号的黑客排名视频,在阅读职业杯的材料时,我总是听到“放下常数”这个词。请让我知道我是否正确理解以下算法:

    function whyWouldIDoThis(array){
     max = NULL
    for each a in array {
      max = MAX(a, max)
    }
    print max
    for each a in array {
      for each b in array {
        print a,b
      }
    }
   }

有人解释说,因为这是两个单独的for循环,那么第一个for循环是o(n),第二个for循环是o(n^2),因为它是一种算法,所以它最终成为o(n^2)。It makes sense that since the term 'n' is the same then they cancel out. 这是“删除内容”的意思吗?

1 回复 | 直到 6 年前

fractals Francisco Flores 6 年前

max = NULL ----------------- c_1
for each a in array {
  max = MAX(a, max) -------- c_2
}
print max ------------------ c_3
for each a in array {
  for each b in array {
    print a, b ------------- c_4
  }
}

一行一行地分析代码,我们得到所用的总时间是

C_1+c_2*n+c_3+c_4*n*n=c_4 n^2+c_2*n+c_1+c_3

现在我们只需要显性项,即c_4n^2,也不需要系数c_4。所以我们有O(n^2)。

在这个意义上,“降低常数”是指系数 . 也就是说,即使您的代码可能比O(n^2),或者O(n^2/2)稍微快一点,但对于大的oh来说并不重要;它都是O(n^2)。

推荐文章

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Dazcii · 如何找到3个嵌套循环的复杂性

6 年前

Kodean · Java:循环字符串长度时间复杂性

6 年前

screeb · 依赖于收敛的算法的大O

7 年前

f1sh3r0 · 从图中确定渐近增长率

7 年前

shinwari_afg · 使用大Oh分析while(key<=N*N)循环的复杂性

7 年前

alekscooper1 · 这里是f(x)=O(g(x))还是反之亦然?

7 年前

user3487554 · 时间复杂性组合

7 年前

user6217340 · 大O复杂性

7 年前

Jawwad Rafiq · 对两个相关循环的复杂性感到困惑?

7 年前