算法复杂度
如果对两个数组进行排序，然后执行线性步骤来记录公共元素，则可以找到两个数组的交集。 这将需要 O(nlogn) + O(nlogn) + O(n)
或者，您可以将第一个数组中的每个元素与第二个数组中的每个元素进行比较，您将获得 O(n^2) 运行时复杂度。
我如何证明第一种方法比第二种方法更好？
Finding intersection of two arrays can be done if you sort the 2 arrays and then do a linear step through to record the common elements.
This would take O(nlogn) + O(nlogn) + O(n)
Alternatively, you could compare each element in the first array with each element in the second array and you would get a O(n^2) run-time complexity.
How can I prove the first approach is better than the second?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
首先，
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)。First of all,
O(nlogn) + O(nlogn) + O(n)doesn't make much sense, sinceO(f)is a set, not a number.What you mean is
O(nlogn + nlogn + n), which can be shown to be equal toO(nlogn). Just look at what it means for a functionfto belong to the setO(g):fis an element ofO(g)iff there existsc>0andx0such that for allx>x0:|f(x)| <= c*|g(x)|By setting
f=nlognandg=nlogn+nlogn+n, it follows thatfis inO(g), and hence thatO(nlogn) == O(nlogn + nlogn + n).重要的是要记住，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)
It's important to remember that Big-O notation is the "worst case" run-time meaning that you are iterating over an array that is crushingly large.
O(N) + O(N) is equivalent to O(2N) which is equivalent to O(N)
Thus, O(nlogn) + O(nlogn) + O(n) is merely O(nlogn)
O(nlogn) < O(n^2)
O(nlogn) + O(nlogn) + O(n) = O(nlogn)
O(nlogn) < c*nlogn
O(n^2) < d*(n^2)
c*nlogn < d*(n^2)
logn logn d/c*n
您可以通过多种方式证明存在一个 N，其中 logn < d/c*n 始终为真。
你甚至可以画出来。
O(nlogn) + O(nlogn) + O(n) = O(nlogn)
O(nlogn) < c*nlogn
O(n^2) < d*(n^2)
c*nlogn < d*(n^2)
logn < d/c*n
You can prove in many ways that there's an N where logn < d/c*n is always true.
You could even draw it.