三角数的大O表示法吗? [英] Big O notation for triangular numbers?

问题描述

对于在三角形时间内运行的算法，正确的大O表示法是什么?这是一个示例:

What's the correct big O notation for an algorithm that runs in triangular time? Here's an example:

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

我的第一个直觉是O(n²)，但我不确定.

My first instinct is O(n²), but I'm not entirely sure.

推荐答案

是的，N *(N + 1)/2，当您删除常量和低阶项时，会留下N平方.

Yes, N*(N+1)/2, when you drop the constants and lower-order terms, leaves you with N-squared.

这篇关于三角数的大O表示法吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！