代码之家 › 专栏 › 技术社区 › zildjohn01

三角数的大O符号?

big-o

zildjohn01 · 技术社区 · 15 年前

triangular 时间?举个例子:

func(x):
  for i in 0..x
    for j in 0..i
      do_something(i, j)

我的第一直觉是 O(nÂ²) ,但我不完全确定。

6 回复 | 直到 15 年前

Brian 15 年前

是的,N*(N+1)/2,当你去掉常数和低阶项,剩下N平方。

Janick Bernet 15 年前

是啊, O(n^2) 绝对正确。如果我没记错的话,O总是一个上界,所以 O(n^3) O(n^n) 或者别的什么。然而 O(n^2)

rajeshnair 15 年前

reece 15 年前

((n+1)^2)/2 . 因此,这是计算时间:O(((n+1)^2)/2)

Serdar Sanli 15 年前

然后算法的运行时间将从t增加到4t

所以算法是O(n^2)

-3

Paul 13 年前

它也可以表示为O(n^2)对我来说这似乎有点误导,因为执行的量总是O(n^2)执行量的一半。

推荐文章

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

3 年前

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

7 年前

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

7 年前

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 年前