Что такое правильное обозначение Big O для этой проблемы?

Question

Я поспорил с другом о следующей проблеме:

Если бы вы запустили бинарный поиск по двум наборам данных неизвестной длины (например, отсортированные массивы m и n) и должны были определить сложность времени для всей функции, что бы это было? Будет ли это O (log (m + n)) или O (log (m)), если m> n, и O (log (n)), если n> m?

Answer 1

Вы выполняете два независимых поиска по двум независимым массивам, а не один поиск по одному большому массиву. Таким образом, сложность двух операций просто складывается вместе - O (log (n)) + O (log (m)). Как вы упомянули, если n> m, сложность m незначительна, и вы останетесь с O (log (n)), и наоборот.

Answer 2

Вы можете просто ответить: O (log (m * n)) = O (log (m) + log (n)) = O (log (m)) + O (log (n)) = Math.max (O (log (m)), O (log (n))).

Answer 3

Это либо O (log (m)), если m> n, либо O (log (n)), если n> m, потому что в общем случае для n элементов мы имеем O (log (n)). наихудший случай означает в худшем случае, до какого элемента он может перейти, который будет n-м или m-м элементом, если любой из двух является максимальным. обратите внимание, что для синхронного значения параллельный, если для асинхронного это будет log (m) + log (n)