Блог

Главная - Вопросы по программированию - Будет ли большая омега переменной, которая является большой омегой второй переменной, быть большой омегой этой второй переменной?

Будет ли большая омега переменной, которая является большой омегой второй переменной, быть большой омегой этой второй переменной?

#complexity-theory

#теория сложности

Вопрос:

Если бы у меня была переменная x, которая, как я знал, была O (y), и я знал, что третья переменная t является большой омегой (x), было бы верно, что t является большой омегой (y)?

Комментарии:

1. Если x <= y и t >= x следует ли из этого t >= y ?

2. Сложность — это свойство функций, а не переменных

Ответ №1:

Нет. Прежде всего, давайте заменим все вхождения «переменной» на функцию, чтобы сделать вопрос значимым. Затем рассмотрим следующий контрпример:

 x(n) = n
y(n) = n^2
t(n) = n

Эти назначения удовлетворяют антецеденту, но не следствию.