Algoritmos: Como somar O (n) e O (nlog (n)) juntos?

22

Eu tenho o seguinte algoritmo que encontra duplicatas e os remove:

public static int numDuplicatesB(int[] arr) {
    Sort.mergesort(arr);
    int numDups = 0;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] == arr[i - 1]) {
            numDups++;
} }
    return numDups;
}

Estou tentando encontrar a pior complexidade de tempo possível. Eu sei que mergesort é nlog(n)e, no meu loop for, estou repetindo todo o conjunto de dados, para que isso conte como n. Não tenho certeza do que fazer com esses números. Devo apenas juntá-los? Se eu fizesse isso, como faria?

algorithms algorithm-analysis big-o helicóptero desenhar lion4
fonte
1
Nota lateral: você pode usar uma tabela de hash para fazer isso em O (n), dependendo dos requisitos de memória.
corsiKa

Respostas:

67 
O(n) + O(n log(n)) = O(n log(n))

Para a complexidade do Big O, tudo o que importa é o termo dominante. n log(n)domina, nentão esse é o único termo com o qual você se preocupa.

Justin Cave
fonte
4
Outra maneira de pensar sobre isso é imaginar que o processamento de O (n) era realmente O (n log n), como se você fizesse dois tipos independentes. Então você teria 2 * O (n log n). Mas as constantes diminuem, então você volta para O (n log n).
Jonathan Eunice
4
@ Jonathan Enquanto isso funciona na prática, é bem verdade que O (n) não é igual a O (n log (n)), então eu não recomendaria usá-lo regularmente.
Aza
17
@Emrakul, na verdade, acho que o raciocínio é teoricamente sólido e prático. O (n) é um subconjunto apropriado de O (n log (n)). Portanto, se f (n) pertence a O (n), também pertence a O (n log (n)).
Emory 9/10
17
Note-se que quando dizemos f(n) is O(g(n))o que realmente estamos dizendo é que a função f is a member of the set of functions that grows at the rate of at most g(n) over the long term. Isso significa que todos os membros de O(n)também são membros de O(n*log(n)). As +expressões in, na O(f(n)) + O(g(n))verdade, referem-se à união de conjunto (qual de vocês é realmente pedante, realmente deve usar ∪).
Lie Ryan
3
@LieRyan Originalmente, ele não está definido união, mas soma set: A + B = { a + b | a in A, b in B }. Ocorre que, para conjuntos da forma, O(g(n))é o mesmo que união de conjuntos, pois um dos conjuntos é sempre um subconjunto do outro, e ambos são invariantes às somas (ou seja, A + A = A). (Opa, Nate escreveu essencialmente o mesmo).
Paŭlo Ebermann 10/10
56

Vamos analisar o caminho e lembrar a definição de O. O que eu vou usar é para o limite no infinito.

Você está certo ao afirmar que executa duas operações com limites assintóticos correspondentes O(n)e, O(nlog(n))mas combiná-las em um único limite não é tão simples quanto adicionar as duas funções. Você sabe que sua função leva pelo menos O(n)tempo e também pelo menos O(nlog(n))tempo. Então, realmente a classe de complexidade para sua função é a união de O(n)e O(nlog(n))mas O(nlog(n))é um super conjunto de O(n)então realmente é apenas O(nlog(n)).

davidk01
fonte
12
+1 essa deve ser a resposta. Ele descreve a resposta com mais precisão usando termos compsci.
5

Se você fosse defini-lo à mão, ficaria mais ou menos assim:

Suponha que o tempo total seja: an + bn log (n), onde aeb são constantes (ignorando termos de ordem inferior).

Como n vai para o infinito (an + bn log (n)) / n log (n) -> a / log (n) + b -> b

Portanto, o tempo total é O (bn log (n)) = O (n log (n)).

richardb
fonte
2

Comece com a definição de O ():

O (n log n) significa "menor que C n log n, se n for grande".

O (n) significa "menor que D n, se n for grande".

Se você adicionar os dois, o resultado será menor que C n log n + D n <C n log n + D n log n <(C + D) n log n = O (n log n).

Em geral, se f (n)> C g (n) para n grande e algum C> 0, então O (f (n)) + O (g (n)) = O (f (n)). E depois de fazer alguns casos usando a definição de O (), você saberá o que pode e o que não pode fazer.

gnasher729
fonte
1

A notação O grande é definida como um conjunto:

insira a descrição da imagem aqui

Portanto, insira a descrição da imagem aquicontém todas as funções que são - começando de algum ponto grande arbitrário insira a descrição da imagem aqui- sempre menores que g.

Agora, quando você tem uma função que está dentro insira a descrição da imagem aquie depois executa outra que aumenta mais devagar que g, certamente está aumentando mais devagar que 2g. Portanto, executar algo mais lento que g não mudará a classe de complexidade.

Mais formalmente:

f, h \ in \ mathcal {O} (g) \ Rightarrow (f + h) \ in \ mathcal {O} (g)

Você pode facilmente provar isso.

TL; DR

Ainda é n log (n)

Martin Thoma
fonte