7

Esse algorítimo serve pra retornar o elemento que mais se repete numa lista:

def algorithm_x(a):
    x = 0
    y = 0
    for i in range(0, len(a)):
        k = 1
        for j in range(i+1, len(a)):
            if a[i] == a[j]:
                k = k + 1
        if x < k:
            x = k
            y = a[i]
    return y

Eu não entendo porque a complexidade dele é considerada O(nˆ2) ao invés de O(nˆ3), visto que no for externo você vai percorrer n vezes, no interno vai percorrer n*n vezes. Multiplicando os dois loops daria n*n*n. Onde estou errando?

2 Respostas 2

7

O interno não percorrerá em n * n, em nenhum lugar mostra isso e é uma inferência sua que faz isso. Já que essa informação não existe no código, você que deveria dizer porque achou isso.

Se tem apenas um laço interno não tem como ele por si só ser polinomial. A não ser que alguma função interna nele na verdade fosse um laço mesmo sem você saber, mas não é o caso, todas funções (e operadores) executadas ali dentro tem complexidade O(1).

Inclusive dizer que é O(n^2) também está errado. A fórmula correta aproximada seria O(n*(n/2)) já que a cada passo ele vai começando percorrer os elementos mais pra frente até que no fim ele começa pelo último elemento, na média ele executa metade dos elementos.

O laço externo vai de 0 até o tamanho da coleção passada. Isso é fácil. Vamos dizer que a coleção tenha 6 elementos, portanto a faixa vai até 5, ela é exclusiva.

O laço interno primeiramente começará em 1 e vai até o 5. No segundo passo do externo o valor de i é 1, então o próximo laço interno começará do 2 e vai até 5. Na próxima vai do 3 até 5, e assim continua até que vai do 5 até 5. Portanto o primeiro percorreu 5 elementos, depois 4, então 3, aí 2, e finalmente 1. Somando tudo dá 15, e para calcular a média dividimos pela quantidade de interações (que foram 5), que dá 3, e que é metade de 6.

Eu dei uma resposta que mostra isso com mais detalhes e um exemplo. Ali fica mais claro a desmistificação que a quantidade de laços usada sempre determina a complexidade. Em alguns casos sim, por isso não serve de modelo, serve como indicação inicial a ser investigada mais. Nos comentários da outra resposta eu mostro como o que parece ser uma complexidade pode ser outra se for mais a fundo, e coincidências não podem ser usadas para demonstrar a complexidade real.

Coloquei no GitHub para referência futura.

12
  • 2
    O(n^2) é equivalente a O(n*(n/2)). Relembrando assíntotas. Então, sim, pode-se dizer que o algoritmo apresentado roda em ordem quadrática e isso estará correto. Também se pode dizer que rodará em função quadrática, visto que qualquer polinômio de grau 2 é uma quadrática (incluindo fator constante e linear). Commented 17/02/2020 às 12:53
  • 2
    Também devo lembrar aqui que a notação Big-O trata-se de conjuntos, não de um polinômio em específico. Portanto, falar que n^2 == O(n^2) é um abuso comum de escrita, quando o correto seria usar n^2 ∈ O(n^2). Como o conjunto descrito por O(n**2) é exatamente o mesmo que o conjunto definido por O(n*(n/2)), podemos escrever sem problemas que O(n^2) == O(n*(n/2)) Commented 17/02/2020 às 12:59
  • 1
    Então você precisa urgentemente revisar sua teoria. Em se tratando de notação assintótica, quick sort é O(n^2), mas não é por isso que você não usará ele para casos garantidamente aleatórios onde ele tem comportamento O(n log n). Também vale ressaltar que a função dentro do grande O deve ser levada em consideração para quando a variável tende ao infinito, então substituir por 6 é simplesmente errado. Vale lembrar que o comportamento assintótico não tem a ver com quantas computações serão realmente feitas, é uma assíntota. Commented 17/02/2020 às 13:27
  • 1
    E, sim, o comportamento assintótico serve para mostrar o quão rapidamente vai crescer o tempo computacional de processamento, e não para dizer que haverão 18 comparações. Note que, se dobrar o n (ou seja, tomar 12 como entrada), ambos os cálculos serão uma multiplicação por 4: 12*12 = (6*2) * (6*2) = 6*6 * 4 e 12*12/2 = 6*2 * 6*2/2 = 6*(6/2) * 4 Commented 17/02/2020 às 13:31
  • 1
    Você poderia dizer que n**2/2 + n/2 aproxima melhor o comportamento que n**2. Usar notação Big-O para isso é abuso (mas como dizer que n**2 == O(n**2) também é abuso e todo mundo faz). De toda sorte, em algoritmos mais complexos, muito comum usar que ele tem comportamento de acordo com O(F(n)) se n <= M e O(G(n)) se M < n. Isso se faz quando, para aquele intervalo de valores específicos, a constante que acompanha F ou G faz com que a função se torne desprezível de algum jeito. Commented 17/02/2020 às 13:51
-1

Quando a gente não entende um conceito, é interessante fazer um modelo:

n = 3
for a in range(0, n):
        for b in range(0, n):
                print ("a", a, "b", b)

A saída deste programa é:

a 0 b 0
a 0 b 1
a 0 b 2
a 1 b 0
a 1 b 1
a 1 b 2
a 2 b 0
a 2 b 1
a 2 b 2

Fica claro que a "complexidade" foi O(n^2), imprimiu 9 linhas (3 vezes 3).

5
  • 2
    Não é uma boa. O código ideone.com/pnYqb5 não é O(n^2), existe coincidência de algum caso específico onde m e n valerem igual poder falar que é n^2, mas está conceitualmente errado e observar esse modelo dessa forma passa uma ideia errada do que é complexidade de algoritmo. O código ideone.com/GMgVx7 é O(n) e faz a mesma coisa, o resultado observado não indica qual é a complexidade.
    – Maniero
    Commented 16/02/2020 às 16:00
  • Ok, mas a pergunta era se dois loops aninhados produziam uma complexidade O(n^2) ou O(n^3), essa era a dúvida. E na minha visão você apenas "desenrolou' (unrolled) minha rotina. Daria pra fazer algo semelhante com um Bubble sort, "escondendo" a complexidade elevando "n" ao quadrado e usando um único loop, o que não o torna O(n).
    – epx
    Commented 16/02/2020 às 17:01
  • 3
    A sua resposta manda a pessoa criar um modelo que dá uma ideia falsa. Complexidade de algoritmo é isso, nem sempre a complexidade visível é a que ocorre de fato. O problema não é a pergunta, é a resposta que manda fazer algo que não só não a responde como induz a pessoa levar isso para outros casos que vão enganá-la, e ainda dá um exemplo diferente que não se encaixa no que está feito na pergunta. Passa a ideia que setem 2 laços é O(n^2), o que é uma possibilidade razoável, mas nem sempre ocorre de fato, que foi o que demonstrei no comentário.
    – Maniero
    Commented 16/02/2020 às 18:01
  • 2
    Eu não falei que o Bubble sort pode virar O(n), eu disse que seu modelo não indica qual deva ser a complexidade, dei um exemplo que isso é furado, não dei um exemplo que isso funciona. Então é um modelo furado, um modelo não pode ser usado p/ provar algo quando hora ele funciona hora não. Sua resposta se baseia nele. Eu não disse q sua resposta mostra a complexidade errada, ela está certa (só não tem algo a ver com a pergunta, mas entendo ser um outro exemplo, a intenção não foi responder a pergunta), eu disse apenas que ela tira uma conclusão que não pode acontecer, só a conclusão é falaciosa
    – Maniero
    Commented 16/02/2020 às 18:03
  • "Eu não entendo porque a complexidade dele é considerada O(nˆ2) ao invés de O(nˆ3)". Essa era a pergunta. E eu respondi, do meu modo.
    – epx
    Commented 17/02/2020 às 16:29

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .