Сложность алгоритма

Question

Поиск пересечения двух массивов можно выполнить, если вы отсортируете два массива, а затем выполните линейный шаг для записи общих элементов.Для этого потребуется O (nlogn) + O (nlogn) + O (n)

В качестве альтернативы, вы можете сравнить каждый элемент в первом массиве с каждым элементом во втором массиве, и вы получите O (n ^2) сложность во время выполнения.

Как я могу доказать, что первый подход лучше, чем второй?

Answer 1

Прежде всего, O(nlogn) + O(nlogn) + O(n) не имеет особого смысла, поскольку O(f) - это набор, а не число.

То, что вы имеете в виду, это O(nlogn + nlogn + n), которое может быть показано как O(nlogn). Просто посмотрите, что означает, что функция f относится к набору O(g):

f является элементом O(g), если существуют c>0 и x0 такие, что для всех x>x0:
|f(x)| <= c*|g(x)|

Устанавливая f=nlogn и g=nlogn+nlogn+n, следует, что f находится в O(g), и, следовательно, O(nlogn) == O(nlogn + nlogn + n).

Answer 2

O (nlogn) + O (nlogn) + O (n) = O (nlogn)

O (nlogn)

O (n ^ 2)

c * nlogn

logn

Вы можетево многих случаях докажите, что есть N, где logn всегда верно.

Вы можете даже нарисовать его.

Answer 3

Важно помнить, что нотация Big-O - это «наихудший случай» времени выполнения, означающий, что вы выполняете итерацию по массиву, который является очень большим.

O (N) + O (N) эквивалентно O (2N), что эквивалентно O (N)

Таким образом, O (nlogn) + O (nlogn) + O (n) - это просто O (nlogn)

O (nlogn)