Uma complexidade de tempo Big-Oh pode conter mais de uma variável?

Digamos, por exemplo, que estou processando strings que requer alguma análise de duas strings. Eu não tenho informações sobre o que seus comprimentos podem acabar sendo, então eles vêm de duas famílias distintas. Seria aceitável chamar a complexidade de um algoritmo ou (dependendo se usamos um algoritmo ingênuo ou otimizado)?O ( n + m $O(n * m)$$O(n + m)$

Do mesmo modo, suponhamos que o algoritmo que escolhemos realmente requer dois estágios - uma fase de configuração na primeira string que nos permite processar qualquer número de outras strings sem incorrer nesse custo inicial. Seria apropriado dizer que tem uma construção seguida por qualquer número de cálculos de ?O ( m $O(n)$$O(m)$

Seria apropriado chamá-los de porque ambos os cálculos são lineares?$O(n)$

Sim, claro. Isso é bom e perfeitamente aceitável. É comum e padrão ver algoritmos cujo tempo de execução depende de dois parâmetros.

Por exemplo, você verá frequentemente o tempo de execução da busca pela profundidade expressa como , onde é o número de vértices e é o número de arestas no gráfico. Isso é perfeitamente válido. O significado disso é que existe uma constante e os números modo que o tempo de execução do algoritmo seja no máximo , para todos os . Em outras palavras, se o tempo de execução exato for , dizemos que se existir modo que e implica$O(n+m)$$n$$m$$c$$n_0,m_0$$c \cdot (n+m)$$n>n_0,m>m_0$$f(n,m)$$f(n,m) = O(n+m)$$c,n_0,m_0$$n>n_0$$m>m_0$$f(n,m) \le c \cdot (n+m)$ .

Sim, é perfeitamente apropriado e aceitável dizer que o primeiro estágio leva tempo e o segundo estágio leva tempo .$O(n)$$O(m)$

Importante: Certifique-se de definir o que e são. Você não pode dizer "este é um algoritmo de tempo " sem especificar o que é. Se não estiver especificado na declaração do problema, você precisará especificá-lo. Por exemplo, consulte algoritmos de gráfico, onde geralmente definimos # de vértices e # de arestas.$n$$m$$O(n)$$n$$n$$n =$$m =$

Tanto quanto você pode chamá-los de tempo , não, claro que não - a menos que você saiba que . Obviamente, se você sabe que , segue-se que ; portanto, um algoritmo de tempo também é um algoritmo de tempo . Mas se não houver garantia de que , não será possível chamá-lo de algoritmo de tempo .m = O ( n ) m = O ( n ) m + n = O ( n ) O ( m + n ) O ( n ) m = O ( n ) O ( n $O(n)$$m = O(n)$$m = O(n)$$m+n = O(n)$$O(m+n)$$O(n)$$m = O(n)$$O(n)$

Isso é coisa básica. Você encontrará tudo isso em livros didáticos de algoritmos.