Por que o pior caso para essa função O (n ^ 2)?

Estou tentando me ensinar como calcular a notação BigO para uma função arbitrária. Encontrei essa função em um livro didático. O livro afirma que a função é O (n ² ). Dá uma explicação do porquê disso, mas estou lutando para segui-lo. Gostaria de saber se alguém pode me mostrar a matemática por trás disso. Fundamentalmente, entendo que é algo menor que O (n ³ ), mas não consegui pousar independentemente em O (n ² )

Suponha que recebamos três seqüências de números, A, B e C. Vamos assumir que nenhuma sequência individual contém valores duplicados, mas que pode haver alguns números que estão em duas ou três das seqüências. O problema da disjunção de três vias é determinar se a interseção das três seqüências está vazia, a saber, que não há elemento x tal que x ∈ A, x ∈ B e x ∈ C.

Aliás, isso não é um problema de lição de casa para mim - esse navio navegou anos atrás:), apenas eu tentando ficar mais esperto.

def disjoint(A, B, C):
        """Return True if there is no element common to all three lists."""  
        for a in A:
            for b in B:
                if a == b: # only check C if we found match from A and B
                   for c in C:
                       if a == c # (and thus a == b == c)
                           return False # we found a common value
        return True # if we reach this, sets are disjoint

[Editar] De acordo com o livro:

Na versão aprimorada, não é apenas uma questão de economizar tempo se tivermos sorte. Afirmamos que o pior caso de interrupção é O (n ² ).

A explicação do livro, que luto para seguir, é a seguinte:

Para explicar o tempo de execução geral, examinamos o tempo gasto na execução de cada linha de código. O gerenciamento do loop for sobre A requer tempo O (n). O gerenciamento do loop for sobre B representa um total de tempo de O (n ² ), uma vez que esse loop é executado n momentos diferentes. O teste a == b é avaliado O (n ² ) vezes. O restante do tempo gasto depende de quantos pares correspondentes (a, b) existem. Como observamos, existem no máximo n pares desse tipo; portanto, o gerenciamento do loop sobre C e os comandos dentro do corpo desse loop usam no máximo o tempo O (n ² ). O tempo total gasto é O (n ² ).

(E para dar o devido crédito ...) O livro é: Estruturas de dados e algoritmos em Python por Michael T. Goodrich et. todos, Wiley Publishing, pág. 135

[Editar] Uma justificativa; Abaixo está o código antes da otimização:

def disjoint1(A, B, C):
    """Return True if there is no element common to all three lists."""
       for a in A:
           for b in B:
               for c in C:
                   if a == b == c:
                        return False # we found a common value
return True # if we reach this, sets are disjoint

No acima, você pode ver claramente que esse é O (n ³ ), porque cada loop deve ser executado ao máximo. O livro afirmaria que, no exemplo simplificado (dado primeiro), o terceiro loop é apenas uma complexidade de O (n ² ); portanto, a equação de complexidade é como k + O (n ² ) + O (n ² ), que finalmente produz O (n ² ).

Embora eu não possa provar que esse é o caso (portanto, a questão), o leitor pode concordar que a complexidade do algoritmo simplificado é pelo menos menor que o original.

[Edit] E para provar que a versão simplificada é quadrática:

if __name__ == '__main__':
    for c in [100, 200, 300, 400, 500]:
        l1, l2, l3 = get_random(c), get_random(c), get_random(c)
        start = time.time()
        disjoint1(l1, l2, l3)
        print(time.time() - start)
        start = time.time()
        disjoint2(l1, l2, l3)
        print(time.time() - start)

Rendimentos:

0.02684807777404785
0.00019478797912597656
0.19134306907653809
0.0007600784301757812
0.6405444145202637
0.0018095970153808594
1.4873297214508057
0.003167390823364258
2.953308343887329
0.004908084869384766

Como a segunda diferença é igual, a função simplificada é de fato quadrática:

[Editar] E ainda mais uma prova:

Se eu assumir o pior caso (A = B! = C),

if __name__ == '__main__':
    for c in [10, 20, 30, 40, 50]:
        l1, l2, l3 = range(0, c), range(0,c), range(5*c, 6*c)
        its1 = disjoint1(l1, l2, l3)
        its2 = disjoint2(l1, l2, l3)
        print(f"iterations1 = {its1}")
        print(f"iterations2 = {its2}")
        disjoint2(l1, l2, l3)

rendimentos:

iterations1 = 1000
iterations2 = 100
iterations1 = 8000
iterations2 = 400
iterations1 = 27000
iterations2 = 900
iterations1 = 64000
iterations2 = 1600
iterations1 = 125000
iterations2 = 2500

Usando o segundo teste de diferença, o pior resultado é exatamente quadrático.

O livro está realmente correto e fornece um bom argumento. Observe que os tempos não são um indicador confiável da complexidade algorítmica. Os tempos podem considerar apenas uma distribuição de dados especial ou os casos de teste podem ser muito pequenos: a complexidade algorítmica descreve apenas como o uso de recursos ou o tempo de execução são dimensionados para além de um tamanho de entrada adequadamente grande.

O livro argumenta que a complexidade é O (n²) porque o if a == bramo é inserido no máximo n vezes. Isso não é óbvio, porque os loops ainda são gravados como aninhados. É mais óbvio se extrairmos:

def disjoint(A, B, C):
  AB = (a
        for a in A
        for b in B
        if a == b)
  ABC = (a
         for a in AB
         for c in C
         if a == c)
  for a in ABC:
    return False
  return True

Essa variante usa geradores para representar resultados intermediários.

• No gerador AB, teremos no máximo n elementos (por causa da garantia de que as listas de entrada não conterão duplicatas), e produzir o gerador leva a complexidade de O (n²).
• A produção do gerador ABCenvolve um loop sobre o gerador ABde comprimento n e acima Cdo comprimento n , de modo que sua complexidade algorítmica também seja O (n²).
• Essas operações não são aninhadas, mas ocorrem independentemente, de modo que a complexidade total é O (n² + n²) = O (n²).

Como os pares de listas de entrada podem ser verificados sequencialmente, segue-se que a determinação de qualquer número de listas disjuntas pode ser feita no tempo O (n²).

Essa análise é imprecisa porque supõe que todas as listas tenham o mesmo comprimento. Podemos dizer com mais precisão que ABtem no máximo comprimento min (| A |, | B |) e produzi-lo tem complexidade O (| A | • | B |). A produção ABCtem complexidade O (min (| A |, | B |) • | C |). A complexidade total depende então de como as listas de entrada são ordenadas. Com | A | ≤ | B | ≤ | C | obtemos total complexidade do pior caso de O (| A | • | C |).

Observe que ganhos de eficiência são possíveis se os contêineres de entrada permitirem testes rápidos de associação, em vez de ter que repetir todos os elementos. Esse pode ser o caso quando eles são classificados para que uma pesquisa binária possa ser feita ou quando são conjuntos de hash. Sem loops aninhados explícitos, isso seria semelhante a:

for a in A:
  if a in B:  # might implicitly loop
    if a in C:  # might implicitly loop
      return False
return True

ou na versão baseada em gerador:

AB = (a for a in A if a in B)
ABC = (a for a in AB if a in C)
for a in ABC:
  return False
return True

Observe que, se todos os elementos forem diferentes em cada uma das listas assumidas, é possível iterar C apenas uma vez para cada elemento em A (se houver um elemento em B igual a). Portanto, o loop interno é O (n ^ 2) total

Assumiremos que nenhuma sequência individual contém duplicado.

é uma informação muito importante.

Caso contrário, o pior caso da versão otimizada ainda seria O (n³), quando A e B são iguais e contêm um elemento duplicado n vezes:

i = 0
def disjoint(A, B, C):
    global i
    for a in A:
        for b in B:
            if a == b:
                for c in C:
                    i+=1
                    print(i)
                    if a == c:
                        return False 
    return True 

print(disjoint([1] * 10, [1] * 10, [2] * 10))

quais saídas:

...
...
...
993
994
995
996
997
998
999
1000
True

Então, basicamente, os autores assumem que o pior caso de O (n³) não deveria acontecer (por quê?) E "provam" que o pior caso é agora O (n²).

A otimização real seria usar conjuntos ou dictos para testar a inclusão em O (1). Nesse caso, disjointseria O (n) para cada entrada.

Para colocar as coisas nos termos que seu livro usa:

Eu acho que você não tem nenhum problema em entender que a verificação a == bé no pior caso O (n ² ).

Agora, na pior das hipóteses, para o terceiro loop, cada ain Atem uma correspondência B, portanto o terceiro loop será chamado sempre. No caso em aque não existe C, ele será executado em todo o Cconjunto.

Em outras palavras, é 1 vez para todos ae 1 vez para todos c, ou n * n. O (n ² )

Portanto, há O (n ² ) + O (n ² ) que seu livro aponta.

O truque do método otimizado é cortar custos. Somente se a e b corresponderem, c será valorizado. Agora você pode descobrir que, na pior das hipóteses, ainda teria que avaliar cada c. Isso não é verdade.

Você provavelmente acha que o pior caso é que toda verificação de a == b resulta em uma execução sobre C, porque toda verificação de a == b retorna uma correspondência. Mas isso não é possível porque as condições para isso são contraditórias. Para que isso funcione, você precisa de um A e um B que contenham os mesmos valores. Eles podem ser ordenados de maneira diferente, mas cada valor em A teria que ter um valor correspondente em B.

Agora aqui está o kicker. Não há como organizar esses valores para que, para cada a, você tenha que avaliar todos os b antes de encontrar sua correspondência.

A: 1 2 3 4 5
B: 1 2 3 4 5

Isso seria feito instantaneamente porque os 1s correspondentes são o primeiro elemento de ambas as séries. Sobre

A: 1 2 3 4 5
B: 5 4 3 2 1

Isso funcionaria para a primeira execução sobre A: apenas o último elemento em B produziria um acerto. Mas a próxima iteração sobre A já teria que ser mais rápida porque o último ponto em B já está ocupado por 1. E, de fato, isso levaria apenas quatro iterações dessa vez. E isso fica um pouco melhor a cada próxima iteração.

Agora eu não sou matemático, então não posso provar que isso acabará em O (n2), mas posso sentir isso nos meus tamancos.

Fiquei perplexo no começo, mas a resposta de Amon é realmente útil. Quero ver se consigo fazer uma versão realmente concisa:

Para um determinado valor de ain A, a função se compara aa todos os bin possíveis Be o faz apenas uma vez. Portanto, para um dado, aele executa a == bexatamente o ntempo.

Bnão contém duplicatas (nenhuma das listas contém), portanto, para um dado a, haverá no máximo uma correspondência. (Essa é a chave). Onde houver uma correspondência, aserá comparado com todos os possíveis c, o que significa que a == cé realizado exatamente n vezes. Onde não há correspondência, a == cnão acontece.

Portanto, para um dado a, há ncomparações ou 2ncomparações. Isso acontece para todos a, portanto, o melhor caso possível é (n²) e o pior é (2n²).

TLDR: todo valor de aé comparado com todo valor de be contra todo valor de c, mas não contra toda combinação de be c. Os dois problemas se somam, mas não se multiplicam.

Pense dessa maneira: alguns números podem estar em duas ou três das seqüências, mas o caso médio disso é que, para cada elemento do conjunto A, uma pesquisa exaustiva é realizada em b. É garantido que todos os elementos do conjunto A serão repetidos, mas está implícito que menos da metade dos elementos no conjunto b serão repetidos.

Quando os elementos do conjunto b são iterados, uma iteração acontece se houver uma correspondência. isso significa que o caso médio para essa função separada é O (n2), mas o pior caso absoluto para ela pode ser O (n3). Se o livro não entrar em detalhes, provavelmente daria a você um caso médio como resposta.