Big O обозначения для треугольных чисел?

Question

Какая правильная запись больших О для алгоритма, который выполняется за треугольное время?Вот пример:

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

Мой первый инстинкт O(n²), но я не совсем уверен.

Answer 1

Да, N * (N + 1) / 2, когда вы отбрасываете константы и члены более низкого порядка, вы получаете N-квадрат.

Answer 2

Да, O(n^2) определенно правильно. Если я правильно помню, O в любом случае всегда является верхней границей, поэтому O(n^3), если IMO также будет правильным, как и O(n^n) или что-то еще. Тем не менее, O(n^2) кажется наиболее узким, легко вычитаемым.

Answer 3

O (! N) обрабатывает случаи для факториального вычисления (треугольное время).Для меня это также может быть представлено как O (n ^ 2), это, кажется, немного вводит в заблуждение, поскольку выполняемая сумма всегда будет вдвое меньше, чем будет выполнять O (n ^ 2).

Answer 4

, когда вход увеличивается от N до 2N тогда время работы вашего алгоритма увеличится с t до 4t

таким образом, время работы пропорционально квадрату входного размера

так что алгоритм O (n ^ 2)

Answer 5

Время вычисления увеличивается для этого кода с коэффициентом N * (N + 1) / 2. По сути это O (N ^ 2).

Answer 6

Если вы думаете об этом математически, площадь вычисляемого треугольника равна ((n+1)^2)/2. Следовательно, это вычислительное время: O (((n + 1) ^ 2) / 2)