算法复杂度

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)。只需看看属于集合O(g)的函数f意味着什么

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

重要的是要记住，Big-O表示法是“最坏情况”的运行时，这意味着您正在迭代一个非常大的数组。

O(N) + O(N)等价于O(2N)，O(2N)等价于O(N)

因此，O(nlogn) + O(nlogn) + O(n)仅仅是O(nlogn)。

O(nlogn) < O(n^2)

Answer 3

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

O(nlogn) < c*nlogn

O(n^2) < d*(n^2)

c*nlogn < d*(n^2)

登录< d/c*n

你可以用很多方法证明存在一个N，其中logn < d/c*n总是真的。

你甚至可以画出来。