Big-Oh обозначение

Question

если T (n) равно O (n), то также правильно сказать, что T (n) есть O (n2)?

Answer 1

Да; потому что O (n) является подмножеством O (n ^ 2).

Answer 2

Предполагая

T (n) = O (n), n> 0

Тогда оба следующих условия верны

T (n) = O (2n)
T (n) = O (n ² )

Это связано с тем, что 2n и n2 растут так же быстро или быстрее, чем просто n. РЕДАКТИРОВАТЬ: Как правильно отмечает Филипп в комментариях, даже значение меньше 1 может быть множителем n, так как постоянные члены могут быть отброшены (они становятся незначительными для больших значений n; РЕДАКТИРОВАТЬ 2: как говорит Оли, все константы незначительны согласно определению O). Таким образом, следующее также true:

T (n) = O (0,2n)

На самом деле n ² растет так быстро, что вы также можете сказать

T (n) = o (n ² )

но не

T (n) = Θ (n ² )

, поскольку данные функции обеспечивают асимптотическую верхнюю границу, а не асимптотически жесткую границу.

Answer 3

если вы имеете в виду O (2 * N), тогда да O (n) == O (2n). Требуемое время является линейной функцией входных данных в обоих случаях

Я не согласен с другим ответом, который говорит, что O (N) = O (N * N). Это правда, что функция O (N) завершится за меньшее время, чем O (N * N), но время завершения не является функцией n * n, поэтому на самом деле это не так

Полагаю, ответ зависит от того, почему вы задаете вопрос

Answer 4

O, также известный как Big-Oh, является верхней границей. Можно сказать, что существует такой C, что для всех n> N T (n)

Таким образом, до тех пор, пока большой коэффициент в T (n) не станет меньше или равен g (n), это утверждение всегда будет действительным.