Considere o seguinte teorema: Teorema. Sejam f₁, f₂, g₁, g₂ funções N o R tais que f₁(n) O(g₁(n)) e f₂(n) O(g₂(n)) . Então f₁(n) + f₂(n) O(\g₁(n), g₂(n)\) .No contexto de análise de algoritmos, o teorema em questão significa que:

Os algoritmos f₁ e f₂ computam, respectivamente, as funções g₁ e g₂ .

As funções f₁ e f₂ encontram o valor máximo das funções g₁ e g₂ .

Considere o seguinte teorema: Teorema. Sejam f₁...

457941204901902

Ano: 2022Banca: UFPROrganização: UFPRDisciplina: Estruturas de Dados e AlgoritmosTemas: Análise de Complexidade

Considere o seguinte teorema: Teorema. Sejam \(f_{1}, f_{2}, g_{1}, g_{2}\) funções \(N o \mathbb{R}\) tais que \(f_{1}(n) \in O(g_{1}(n))\) e \(f_{2}(n) \in O(g_{2}(n))\). Então \(f_{1}(n) + f_{2}(n) \in O(\max\{g_{1}(n), g_{2}(n)\})\).

No contexto de análise de algoritmos, o teorema em questão significa que:

As partes mais lentas e rápidas do algoritmo juntas definem o tempo de execução.

A parte mais rápida do algoritmo define o tempo de execução.

A parte mais lenta do algoritmo define o tempo de execução.

Os algoritmos \(f_{1}\) e \(f_{2}\) computam, respectivamente, as funções \(g_{1}\) e \(g_{2}\).

As funções \(f_{1}\) e \(f_{2}\) encontram o valor máximo das funções \(g_{1}\) e \(g_{2}\).

Gabarito comentado

Comentários

Anotações

Enviar para caderno

Reportar erro