Может ли сложность времени Big-Oh содержать более одной переменной?

Скажем, например, я занимаюсь обработкой строк, которая требует некоторого анализа двух строк. У меня нет никакой информации о том, какова их длина, поэтому они происходят из двух разных семей. Было бы приемлемо назвать сложность алгоритма или O ( n + m ) (в зависимости от того, используем ли мы наивный или оптимизированный алгоритм)?$O(n * m)$$O(n + m)$

Аналогичным образом, давайте предположим, что выбранный нами алгоритм на самом деле требует двух этапов - фазы установки первой строки, которая позволяет нам обрабатывать любое количество других строк, не неся при этом первоначальных затрат. Было бы целесообразно сказать, что он имеет конструкцию за которой следует любое количество вычислений O ( m ) ?$O(n)$$O(m)$

Было бы уместно просто назвать их потому что оба вычисления линейны?$O(n)$

Ну конечно; естественно. Это хорошо и вполне приемлемо. Распространено и стандартно видеть алгоритмы, время работы которых зависит от двух параметров.

Например, вы часто будете видеть время выполнения поиска в глубину, выраженное как , где n - количество вершин, а m - количество ребер в графе. Это совершенно верно. Смысл этого в том, что существует постоянная c и числа n 0 , m 0, такие что время работы алгоритма не более c ⋅ ( n + m ) для всех n > n 0 , m > m $O(n+m)$$n$$m$$c$$n_0,m_0$$c \cdot (n+m)$$n>n_0,m>m_0$, Другими словами, если точное время выполнения равно , мы говорим, что f ( n , m ) = O ( n + m ), если существует c , n 0 , m 0 такое, что n > n 0, и m > m 0 подразумевает f ( n , m ) ≤ c ⋅ ( n + m $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)$,

$O(n)$$O(m)$

$n$$m$$O(n)$$n$$n$$n =$$m =$

$O(n)$$m = O(n)$$m = O(n)$$m+n = O(n)$$O(m+n)$$O(n)$$m = O(n)$$O(n)$

Это основные вещи. Вы найдете это по всем учебникам алгоритмов.