Assintótica Notation - se n (log n) (log n) simplificar?

Question

Se eu tiver um algoritmo que leva n log n etapas (por exemplo heapsort), onde os passos levam log n tempo (por exemplo comparação / troca de "grandes" números inteiros na faixa de 0 a n-1), o que é o assintótica obrigado por todo o processo.

Obviamente podemos dizer "n (log n) (log n)", mas eu estou tendo um momento difícil tentando me convencer de que eu não posso simplificar este com "n log n". Ao mesmo tempo, eu estou tendo dificuldade em justificar o instinto que insiste que eu puder.

É o meu instinto apenas errado liso sobre isso?

Editar

Parece que minha simples exemplo-para evitar complicar-the-problema complicou a questão. Oh bem.

A verdadeira razão para a questão é que eu muitas vezes têm um algoritmo padrão com uma complexidade conhecida, mas implementadas usando diferentes recipientes subjacentes, de modo que os passos individuais são O (log n) em vez de O (1). Por exemplo, Hopcrofts autômato minimização algoritmo é O (n log n) - mas se você começar a usar recipientes árvore binária para os estados, transições e resultados intermediários, os passos tornam-se O (log n) - O (n log n) é já não é válida porque o pressuposto de o (1) acessa é inválido.

Ainda, as pessoas vão afirmam que existem n estados e m transições, mas n e m tendem a ser linearmente relacionado por autómatos, assumindo que o número de notas de transição é constante e que os autómatos são mais-ou-menos determinista.

Eu não ter se preocupado muito com isso no passado - os casos com quem trabalho não são muito grandes. Mas, bem, eu estou fazendo uma grande refatoração do meu código autômatos, e eu pensei que eu poderia muito bem fazer a matemática corretamente para alguns algoritmos de chave como eu ir.

Editar

Estou também cada vez mais convencido de que o "n (log n) (log n)" está errado.

Se um é O (b log b) onde b é O (log c), o que é um em termos de c?

Answer 1

Aqui está uma prova por contradição:

Vamos dizer que uma função f (n) = n (log n) (log n). Suponha que nós pensamos que é também teta (n log n), então, em outras palavras, há um um para o qual f (n) <= a * n log n vale para n grande.

Agora, considere f (2 ^ (a + 1)):

f (2 ^ (a + 1)) = 2 ^ (a + 1) * log (2 ^ (a + 1)) * log (2 ^ (a + 1)) = 2 ^ (a + 1 ) * log (2 ^ (a + 1)) * (a + 1), que é claramente maior do que um 2 ^ (a * log + 1) * (2 ^ (a + 1)), e que tem uma contradição . Por conseguinte, F (n) não é uma função de log n n.

Answer 2

Em geral, você não pode complexidades multiplicam como este: para pilha tipo, N indica o número de itens na pilha, enquanto que para os grandes números inteiros, N provavelmente indica o limite superior de valores possíveis. Em geral, estes não devem ser relacionados, de modo que é bastante N log N log M (onde M é o intervalo que os itens podem tomar).

Em uma aplicação específica, muito provavelmente, os grandes inteiros seguem alguma distribuição específica. Por exemplo, pode ser conhecido que todos eles estão abaixo de 10 ^ 20. Se assim for, as operações de comparação ter tempo constante (determinada por um limite superior de 10 ^ 20). Em seguida, log M também é constante, e toda a complexidade está em O (N log N).

Answer 3

Você não será capaz de reduzir n (log n) (log n) para n (log n) simplesmente porque isso não é uma redução por um fator constante.

O que há de errado com n (log n) 2 ?

Answer 4

Ok, a medida geral complexidade de um programa é o seguinte:

complexidade O (f (n)) significa, que existe c, de tal modo que o número dos passos da máquina correspondente Turing antes que termine não é mais do que c * f (n), onde n é o comprimento de entrada.

Nesta definição tudo é levado em conta, porque os números inteiros podem ser arbitrariamente grande, e operações aritméticas sobre eles também aumentaria a função em O (n).

Mas se estivéssemos programação Turing máquinas diretamente, a sua pergunta não teria sido surgido. No mundo real nós preferimos abstrato. Enquanto nós ainda calcular "passos" que são necessários para executar o programa, vamos supor que certas operações têm um passo . Supomos que por razões diferentes:

• pode assemelhar-se o trabalho real da CPU, onde cada adição inteiro de 32-bit é efectivamente um passo (e existem algoritmos que, na verdade, que abusam de, por exemplo, "dominantes bits verctor").
• comparar diferentes algoritmos no mesmo domínio (por exemplo, comparando ordenações de matriz, medindo o número de comparações).

Neste caso (sua primeira edição), se você quiser concretizar a sua medida de complexidade, você deve apenas funções se multiplicam sob O. Se o que você pensou que dar um passo agora considerado a tomar O (log n) passos, então o quantidade de passos concretizados aumenta por um factor de O (log N). Por conseguinte, a complexidade total é O (N log N log N).

---

Quanto à sua segunda EDIT, é uma situação diferente. Deixe seu algoritmo de ser uma complexidade de O (n log N). Mas você sabe que a entrada consiste de números M, cada um dos dígitos log K, então `N = O (M log K) (precisamos conta separadores, etc). É matematicamente correto, em seguida, escrever a complexidade global como O (M * log K * (log M + log log K)), então não há nenhum problema aqui. Mas normalmente nós abstratas detalhes longe desnecessários para encontrar uma base comum para diferentes algoritmos para ser comparado.