Как правильно оценить временную сложность алгоритма?

Question

[NameOf Var]

Пусть имеется главная функция main (с которой начинается запуск программы). В этой функции вызываются последовательно функции func1() и func2(). Функция func1() реализована примерно таким образом:

void func1()
{
     ...
     for (int i = 0; i < n; i++)
          for (int j = 0; j < m; j++)
               { ... }
     ....
}

Т.е. временная сложность будет составлять N*M.
Функция func2() реализована также, но зависит уже от других входных параметров, т.е.

void func2()
{
     ...
     for (int i = 0; i < k; i++)
          for (int j = 0; j < l; j++)
               { ... }
     ....
}

Т.е. временная сложность в данном случае K*L.
Вопрос: какова будет общая сложность алгоритма в целом (т.е. временная сложность функции main)? Правильно ли утверждать, что в таком случае сложность алгоритма будет составлять N*M + K*L?

Answer 1

[Mercury13]

В общем случае да. Но иногда подобные оценки можно упростить. И упрощения можно делать по двум статьям:
1. Более точные оценки. В данном случае не могу придумать.
2. Более простые оценки: ведь оценка — это символ Ландау O(f(·)), который с точностью до константы. Если, например, K<N, а L<M, то сложность будет просто N·M.

Answer 2

[Андрюха]

Наверное мат ожидание E[KL], что если они (K и L) независимы то Е[K]E[L]

Answer 3

[tomatho]

Всё же зависит от того, что в скобках. Если там какие-то условия или циклы, то может оказаться:

• Дополнительный множитель, из-за того, что выполняется сложная операция.
  
• Уберётся множитель, из-за того, что при выполнении некоторого условия выполняется код который сильно дольше проверки этого условия.
  

И это далеко не редкость, когда циклов три, а сложность как будто циклов всего два.
Простейший пример поиск в ширину (bfs). В нём идёт цикл по вершинам, в котором идёт цикл по рёбрам вершины, то есть в худшем случае получается O(N*M) где N - количество вершин, а M количество рёбер, однако очевидно, что это всего лишь O(N+M), Но я хотел подчеркнуть, что это получается из-за того, что в данном алгоритме каждое ребро проходится максимум два раза: O(2M) = O(M), а каждая вершина максимум один раз O(N).