Questão 1/10 - Estrutura de Dados

"A análise de um algoritmo geralmente conta com apenas algumas operações elementares e, em muitos casos, apenas uma operação elementar... Além disso, essa análise costuma ser feita tendo como base um modelo independente de máquina; isto é, a expressão de consumo de tempo é feita abstraindo particularidades como a linguagem de programação, os detalhes de implementação e o computador utilizado. Esse modelo de computação, conhecido como RAM (do inglês random access machine, ou máquina de acesso aleatório, em língua portuguesa), assume os seguintes custos associados às operações executadas por um computador (SKIENKA, 2008):

Cada operação simples (operações aritméticas, comparações e invocações de métodos) custam exatamente um passo de tempo.

Laços (loops) e sub-rotinas não são considerados operações simples. Ao contrário, eles são a composição de múltiplas operações de um passo de tempo. Assim, o tempo necessário para executar um laço ou um subprograma depende do número de iterações do laço ou da natureza específica do subprograma.

Cada acesso à memória requer exatamente um passo de tempo.

Serpa, Matheus da, S. et al. Análise de Algoritmos. Disponível em: Minha Biblioteca, Grupo A, 2021.pag 51-52

Observe o algoritmo abaixo escrito em linguagem Pyhton:

1 def exercicios1(dados)
2 for i in range(0,len(dados),1):
3 if dados[i] > 0:

Com base no texto e no código fornecido, considerando ainda que n é a quantidade de elementos em dados, é correto afirmar:

I. A complexidade para a linha 2 é O(n).

II. A complexidade na linha 2 é O(n/2).

III. A complexidade da linha 3 é O(1).

IV. A complexidade do algoritmo é O(n+1).

Estão corretas as afirmativas: