Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Reno70

[Resolvido] Complexidade de uma função

Mensagens Recomendadas

Reno70

Boa tarde eu tenho algumas duvidas sobre fazer a complexidade de uma função[ O(n) ].

Por exemplo , casos como estes :

#Caso 1. Isto influencia a complexidade de uma função?

[elemento[0] for elemento in dados]

Tenho uma função com o codigo acima , um counter e um sort. A complexidade dessa função é O(n) ou nao ?

Outro caso:

#Caso 2. Volto a ter 3 exemplos como o de cima mas mais um for com um if la dentro.

datas= sorted(dados, key = lambda x: x[3])

kg= [elemento[4] for elemento in datas]
names= [elemento[0] for elemento in datas]

for i in range(...):
 if ...:
 ....
return ...

Gostava que alguem me pudesse ajudar nas complexidades destas duas funções. Muito obrigado

Editado por Reno70

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pwseo

As tuas questões não são completamente claras; tenta especificar melhor o que pretendes saber.

E já agora, qual é a tua opinião sobre a resposta correcta às questões que colocaste?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Reno70

pwseo, tenho duas funções e gostava de saber a complexidade de cada uma delas. Estas duvidas surgem porque nao sei se casos como os seguintes contam/interessam para a complexidae [ O(n) ]

var = [elemento[0] for elemento in dados]

Editado por Reno70

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pwseo

Reno70,

Sabes o que significa dizer que uma função tem complexidade O(n)? É importante percebermos o que sabes sobre o assunto da complexidade.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Reno70

Sinceramente não é muito o que sei porque isso e que tenho duvida, o que sei vi aqui ha uns meses atras , que tinha a for com ciclos , quanto mais ciclos maior é o "n". Mas não sei se é isso , podes ajudar ?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pwseo

Posso ajudar, claro.

De uma forma muito sucinta, dizer que uma função tem complexidade (temporal) de O(n) significa que o seu tempo de execução é directamente proporcional a n, o número de elementos sobre os quais ela opera.

Concretamente, se tens um ciclo for com n iterações (como acontece quando queres, por exemplo, duplicar cada número numa lista), a complexidade temporal será O(n).

Tudo bem até aqui? Óptimo!

Imagina agora que tens dois ciclos for:

def func(lista):
   for i in lista:
       for j in lista:
           ...

Neste caso temos uma complexidade temporal O(n²) porque o teu código percorre a lista n×n = n² vezes.

E agora a parte final.

Quando tens uma função que utiliza várias funções dentro de si, tens que somar as complexidades, e ficas com o termo de maior grau.

Por exemplo, se tu utilizas um ciclo for (que tem O(n)) numa função e depois tens mais à frente algo com complexidade O(n²), a complexidade conjunta será algo como O(n + n²). Ora, à medida que n tende para o infinito, um dos termos vai crescer muito mais depressa que o outro: o , daí que possamos dizer que a complexidade é de O(n²) (pois para valores de n infinitamente grandes, o termo vai ser tão grande que o n é desprezável).

Dúvidas?

PS.: Há muita formalidade matemática envolvida neste tópico que desconheço. Aquilo que te expliquei foi a visão leiga do tema, isto porque nunca tive formação nesta área.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Reno70

Tenho estas duas funções


def participacoes(dados):

   lista_nomes = [elemento[0] for elemento in dados]
   dicionario_participacoes = Counter(lista_nomes)
   nomes_ordenados = sorted(dicionario_participacoes)

   return [dicionario_participacoes[x] for x in nomes_ordenados]

def calorias_acumuladas(dados,nome):
   datas_ordenadas = sorted(dados, key = lambda x: x[3])

   calorias = [elemento[4] for elemento in datas_ordenadas]
   nomes = [elemento[0] for elemento in datas_ordenadas]

   total = 0
   lista_final = []
   for i in range(len(datas_ordenadas)):
		 if nome == nomes[i]:
				 total = total + calorias[i]
				 lista_final.append(total)
   return lista_final

É impressão minha ou a complexidade das duas é muito alto uma vez que tenho muitos fors? O(4n) para a primeira e O(3n) para a segunda , está certo ?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pwseo

Está quase certo, mas não consideramos isso muito alto.

Se reparares bem, estás a dar uma complexidade de O(4n) para a primeira e O(3n) para a segunda. Normalmente os factores constantes são removidos, o que significa que tens complexidade O(n) em ambas, o que na prática (independentemente do número que pudesses colocar antes do n) será muito inferior a, por exemplo, O(n²) para valores muito altos de n.

PS.: na 2ª função não seria O(3n) porque a sorted() também não é O(1).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Reno70

Então posso mesmo dizer que a complexidade das minhas funções é O(n) nas duas? E justifico como ? Não havendo ciclos encadeados , as funções tem um crescimento linear ,sendo que cada ciclo for executa n vezes ?

Editado por Reno70

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pwseo

Repara: n, 2n, 3n, 4n, 5n, 6n, ..., Xn (para qualquer valor constante de X) continua a ser crescimento linear (dica: se fizeres um gráfico de qualquer uma dessas funções, o gráfico é uma linha).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.