Análise de Complexidade de programas

[jonhhy]

def triangletype(s1,s2,s3):
  if s1 == s2 and s2 == s3:  # Equilátero 2 ops Best case |  Isosceles 1op Best Case  2 ops Worst Case | Scalene 1 op
    print('Equilateral')
  elif s1 == s2 or s1 == s3 or s2 == s3: # Isosceles Best Case: 1op , 3op Worst Case | Escaleno 3ops
    print('Isosceles') # 3 ops BestC  | 4ops WorstC  ... combinando as condições poderá até dar em 2ops mas tlv piorá-se noutros casos  
  else:
    print('Scalene') # 4ops + print
# entre 2 e 4 ops à partida
def triangletype2(s1,s2,s3):
  if s1 == s2: # 1op
    if s1 == s3: 
      print('Equilateral') # 2ops
    else: print('Isosceles') #  2 ops 
  elif s1 == s3 or s2 == s3: # 1+[1,2]=[2,3] ops resulta de 
    print('Isosceles')
  else: print('Scalene') # 3 ops + print

Bom dia a todos,

 

gostaria de saber mais informações sobre a análise de complexidade de programas e algoritmos, de modo, por exemplo qual destes programas é o mais eficiente.

Edited February 15, 2022 at 10:11 AM by jonhhy

[jonhhy]

Obtive esta resposta no dia de ontem:

"Hey! I slightly prefer the flat variant. Also, I guess, the cyclomatic complexity of the first variant will be lower

https://en.wikipedia.org/wiki/Cyclomatic_complexity

In Python, you can measure it with https://pypi.org/project/radon/ or https://pypi.org/project/mccabe/"

 

 

Enquanto isso estou a analisar o conteúdo desta unidade curricular: dcc.fc.up.pt/~pribeiro/aulasdaa2021

Edited February 9, 2022 at 08:39 AM by jonhhy

[jonhhy]

Estará correto (parêntesis)?

interpretado a partir do slide 21 https://www.dcc.fc.up.pt/~pribeiro/aulas/daa2021/slides/1_analiseassintotica_05102020.pdf


https://ibb.co/B6LjSNZ

 

P.s: aqui ganhou significa ser mais complexo ou seja menos eficiente

 

EDITE: Meu raciocínio estava errado aqui, estava a pensar em ciclos

Edited February 15, 2022 at 10:12 AM by jonhhy

[Rui Carlos]

Quando se pensa em eficiência, a complexidade que normalmente interessa é a complexidade temporal.  A complexidade ciclomática e similares estão relacionada com a facilidade de ler/manter o código.

 

Em termos de complexidade temporal, as versões são equivalentes.

[jonhhy]

Obrigado pelas indicações Rui Carlos  👍

estive a analisar com mais cuidado, após ler este artigo (que está muito bom),

fazendo os cálculos como comentários no código... e concluo (o raciocínio) que a 2ª função está otimizada/refinada comparativamente à 1ª a nível complex. temporal

[Rui Carlos]

O(2) = O(3) = O(4) = O(123456789) = O(1)

Por isso, ambas as tuas soluções tem a mesma complexidade temporal (complexidade constante, habitualmente expressa como O(1)).

[jonhhy]

21 horas atrás, Rui Carlos disse:

O(2) = O(3) = O(4) = O(123456789) = O(1)

Por isso, ambas as tuas soluções tem a mesma complexidade temporal (complexidade constante, habitualmente expressa como O(1)).

Certo entendi a ideia, obrigado pela ajuda  👍