Большая нотация O для треугольных чисел?
Какова корректная большая нотация O для алгоритма, который работает в треугольное время? Вот пример:
func(x):
for i in 0..x
for j in 0..i
do_something(i, j)
Мой первый инстинкт O(n²), но я не совсем уверен.
5 ответов
Да, N * (N + 1) / 2, когда вы отбрасываете константы и младшие члены, у вас остается N-квадрат.
Ага, O (n ^ 2) определенно верно. Если я правильно помню, O в любом случае всегда является верхней границей, поэтому O (n ^ 3) также должен быть правильным IMO, как и O (n ^ n) или что-то еще. Однако O (n ^ 2) кажется наиболее точным, который легко вывести.
Если подумать математически, площадь вычисляемого треугольника равна ((n + 1) ^ 2) / 2 . Следовательно, это время вычислений: O (((n + 1) ^ 2) / 2)
Время вычисления увеличивается в N * (N + 1) / 2 раз для этого кода. По сути, это O (N ^ 2).
когда входные данные увеличиваются с N до 2N то время работы вашего алгоритма увеличится с t до 4t
таким образом, время работы пропорционально квадрату размера входа
поэтому алгоритм является O( n^2 )