Временная сложность двух алгоритмов, работающих вместе?

Question

Представьте себе, что T ₁ (n) и T ₂ (n) являются временами выполнения программ P ₁ и P ₂ , и

T ₁ (n) ∈ O (f (n))

T ₂ (n) ∈ O (g (n))

Какова сумма T ₁ (n) + T ₂ (n), когда P ₁ проходит вдоль стороны P ₂

Ответ O(max{f(n), g(n)}) но почему?

Answer 1

Когда мы думаем о нотации Big-O, мы обычно думаем о том, что делает алгоритм, так как размер ввода n становится действительно большим. Много раз мы можем прибегнуть к какой-то интуиции с математикой. Рассмотрим две функции: одну O(n^2) и одну O(n). Когда n становится действительно большим, оба алгоритма увеличиваются без ограничений. Разница в том, что алгоритм O(n^2) сильно растет, НАМНОГО быстрее, чем O(n). Фактически, настолько, что если вы объедините алгоритмы во что-то, что будет O(n^2+n), коэффициент n сам по себе будет настолько мал, что его можно будет игнорировать, и алгоритм все еще находится в классе O(n^2).

Вот почему, когда вы складываете два алгоритма, общее время выполнения составляет O(max{f(n), g(n)}). Всегда есть один, который «доминирует» во время выполнения, делая влияние других незначительным.

Answer 2

Ответ: O (max {f (n), g (n)})

Это верно только в том случае, если программы работают независимо друг от друга.Во всяком случае, давайте предположим, что это так.

Чтобы ответить на вопрос , почему , нам нужно поближе взглянуть на то, что представляет BIG-O-нотация .Вопреки тому, как вы это указали, представляет не время , а верхний предел сложности .

Так что выполнение обеих программ может занять больше времени, верхний пределсложность не увеличится.

Давайте рассмотрим пример: P_1 вычисляет произведение всех пар n чисел в векторе, оно реализовано с использованием вложенных циклов и поэтому имеет сложность O(n*n),P_2 просто печатает числа в одном цикле и поэтому имеет сложность O(n).

Теперь, если мы запустим обе программы одновременно, вложенные циклы P_1 являются наиболее «сложными» часть, оставляя комбинацию со сложностью O(n*n)