Análise de tempo de execução de um simples algoritmo de busca binária

Question

Estou preso com o seguinte problema por Skiena (o manual de design de algoritmo, p. 106):

.

Problema: Dê um algoritmo eficiente para determinar se dois conjuntos (de Tamanho $ m $ e $ n $ , respectivamente) são disjuntos. Analisar o pior caso complexidade em termos de $ M $ e $ n $ , considerando o caso em que $ m $ é substancialmente menor do que $ n $ .

Solução: Primeiro classifique o conjunto grande - o grande conjunto pode ser classificado $ o (n \ log n) $ tempo. Podemos agora fazer uma busca binária com cada um dos m elementos no segundo, olhando para ver se existe no grande conjunto. O tempo total será $ o ((n + m) \ log n) $ .

minha pergunta: por que o tempo de execução $ O ((n + m) \ log n) $ ? Eu teria que executar m buscas binárias no total (uma busca binária para cada elemento em $ m $ ) - como uma pesquisa binária tem um tempo de execução de $ o (\ log n) $ , eu teria que executar $ m \ cdot \ log n $ operações no pior caso. Como isso - se em tudo - traduzir para $ o ((n + m) \ log n) $ ?

Answer 1

Classificação do conjunto Grande leva tempo $ o (n \ log n) $ .Você executa $ M $ Buscas binárias, cada uma que toma $ o (\ log n) $ , para um totalde $ o (m \ log n) $ tempo gasto na busca binária.O tempo total de execução do algoritmo é, portanto, $$ O (n \ log n + m \ log n)= o ((n + m) \ log n)= o (n \ log n), $$ Assumindo $ m \ leq n $ .

Observe que é ainda melhor classificar a lista menor, uma vez que o tempo de execução melhora para $ o (n \ log m) $ .