Soma regra para Big-O com igual complexidade-funções?

Question

Uma propriedade do Big-O-notação é a soma regra, que afirma que quando eu tiver duas funções $f_1$ e $f_2$ e suas correspondentes funções de complexidade são $g_1$ e $g_2$, e , em seguida, o combinado complexidade é $f_1 + f_2 = O(\max(g_1, g_2))$.

Mas o que nós escolher se tanto complexidade-funções são iguais?E. g., se $f_1(n)$ é a ordenação de um array e $_f2(m)$ bem, em seguida, as complexidades são $O(n\log(n))$ e $S(m\log(m))$.Aplicando a regra seria $O(\max(n\log(n), m\log(m)))$.Eu acho que assim qualquer um desses seria produzir um válido, mas muito intuitivo estimativa de como você iria soltar uma variável.Além disso, não está claro que para escolher.

É o caso que você não deve usar a regra quando há muitas variáveis envolvidas?

Answer 1

Ele depende de algumas variáveis sobre depende de outro, ou se eles são fornecidos como parâmetros do problema.Por exemplo, em muitas gráfico de problemas relacionados com a $n$ pode ser o número de vértices, e $m$ pode ser o número de arestas.Neste caso, $m$ pode ser tão grande como $O(n^2)$.Assim, no caso geral, dizer se temos um algoritmo cuja primeira fase é executado no $S(n)$ e a segunda fase é executado no $S(m)$, nós acabamos de adicionar os dois termos juntos e não tente simplificar --- tempo de execução final é $O(n+m)$.

Em termos de várias variáveis fornecidos como parâmetros que não são necessariamente relacionados:eaving várias variáveis dentro da equação final é padrão, ex:Posso dizer que a multiplicação de um $m imes n$ matriz e um $n imes p$ matriz demora $O(mnp)$tempo usando livros didáticos de multiplicação, ou para a solução da mochila problema leva $S(nt)$-tempo onde $n$ é o número de itens e $t$ é o destino de soma.

Em casos especiais, como planar gráficos e outras esparsas gráficos, sabemos que $m=O(n)$, e , assim, podemos substituir com segurança $n$ em lugar de $m$ no final do tempo de execução para a simplificação.

Como uma digressão, isto ilustra por que em grafos esparsos (onde $m=O(n)$) seria de preferir usar Dijktra em um loop para todos os pares de caminho mais curto (em contraste com um transitiva-encerramento algoritmo baseado gosta de Floyd-Warshall);desde agora Dijkstra é executado no $S(m log n) = O(n log n)$, a complexidade total para o uso de Dijkstra em um loop torna-se $O(n^2 log n)$, que é melhor do que o de Floyd-Warshall.Por outro lado, nota que Dijkstra é executado no $m log n$ para o caso geral, o que significa que em densas gráficos onde $m=O(n^2)$, ele se torna menos eficiente do que o de Floyd-Warshall em termos de pior caso do tempo de execução.

Em outros casos, pode haver variáveis não são mesmo polinominalmente delimitada por um determinado parâmetro --- tirar a mochila exemplo acima, onde $t$ pode ser exponencial em $n$.

Answer 2

Não existe uma resposta.A propósito, se você quer simplificar o $O(\max(n\log(n), m\log(m)))$, você pode reescrevê-la como $O((n+m) \log(n+m))$.

Além disso, se $g_1$ e $g_2$ são eqaul e o aumento de funções, você pode escrever $O(g_1(n+m))$ em vez de $O(\max(g_1(n), g_2(m)))$.

Answer 3

Por definição $O(g)$ deve ser sempre variável definida e ponto limite com relação a está a considerar $O$.Por exemplo, em $O(n^3), n o \infty$ variável é $n$ e do ponto-limite $\infty$.No $S(x^3), x o 0$ variável é $x$ e do ponto-limite $0$.

Assim, quando escrevemos $f=O(g)$, e , em seguida, formalmente, queremos dizer algumas variáveis e alguns de ponto-limite.Por exemplo $f(n)=O(g(n)), n o \infty$ é exato do registro.Note, que registrar $f(m)=O(g(m)), m o \infty$ significa exatamente o mesmo da frase anterior.

Quando estamos falando sobre propriedade $f_1 + f_2 = O(\max(g_1, g_2))$, e , em seguida, aqui também deve ser declarada de alguma variável(s) e alguns de ponto-limite.Para registro exato deve ser algo como $$f_1(n) + f_2(n) = O(\max(g_1, g_2)(n)), n o \infty$$ Ou precisamos de mais esclarecimentos com relação às variáveis, supondo que o ponto-limite $\infty$.