Интервью вопросы

Question

Это вопрос интервью:

Given: f(n) = O(n) 
     g(n) = O(n²) 
find f(n) + g(n) and f(n)⋅g(n)? 

Что бы ответ на этот вопрос?

Answer 1

Когда этот ответ был подготовлен, f (n) был показан как o (n) и g (n) как Θ (n²).

Из f (n) = o (n) и g (n) = Θ (n²) вы получаете нижнюю границу o (n²) для f (n) + g (n), но вы не получим верхнюю оценку на f (n) + g (n), потому что на f (n) не была указана верхняя граница. [Обратите внимание, что в выше, Θ является большой-θ или большой тетой)

Для f (n) · g (n) вы получаете нижнюю границу o (n³), потому что Θ (n²) подразумевает нижнее и верхние границы o (n²) и O (n²) для g (n). Опять же, никакая верхняя граница на f (n) · g (n) не доступна, так как f (n) может быть сколь угодно большим; для f (n) мы имеем только нижнюю оценку o (n).

С измененным вопросом, чтобы дать только верхние оценки по f и g, так как f (n) = O (n) и g (n) = O (n²), имеем f (n) + g (n) представляет собой O (n²), а f (n) · g (n) - O (n³).

Чтобы показать это строго, немного утомительно, но довольно прост. Например, для случая f (n) · g (n) предположим, что по определениям O (n) и O (n²) заданы C, X, K, Y такие, что n> X ⇒ C · n> f (n) и n> Y ⇒ K · n²> g (n). Пусть J = C · K и Z = max (X, Y). Тогда n> Z ⇒ J · n³> f (n) · g (n), что доказывает, что f (n) · g (n) равно O (n³).

Answer 2

O(f(n) + g(n)) = O(max{f(n), g(n)}) 

так для первого

f(n) + g(n) = O(max{n, n^2}) = O(n^2) 

для

f(n) ⋅ g(n) 

мы будем иметь

O(f(n) ⋅ g(n)) = O(n ⋅ n^2) = O(n^3) 

Answer 3

Подумайте об этом таким образом.

F (п) = сп + д
г (п) = ап^2 + Bn + р

Затем
F (N) + г (п) = ап^2 + (нижняя полномочия п)
И,
е (п) .g (п) = х^3 + (нижние силы п)

Отсюда следует, что о (е (п) + д (п)) = O (n^2)

и O (f (n) .g (n)) = O (n^3)

Answer 4

Этот вопрос можно понять, как это: -

F (п) = О (п) означает, что требуется O (п) для вычисления F (п).

Аналогично,

для г (п), который требует O (N^2) Время

Так,

Р (п) = е (п) + g (n) определенно примет O (n) + O (n^2) + O (1) (для сложения, , как только вы знаете значение как f, так и g)

. Следовательно, эта новая функция

P (n) потребует времени O (n^2).

То же самое имеет место для

Q (N) = F (п) * г (п), который требует O (N^2) Время

.