寻找任何算法难题的时间复杂度的严格下限？
Finding tight lower limit for time complexity of any algorithmic puzzle?
这是我求职面试中的一个问题。
你如何找到两个数组中的共同元素？你如何证明这个解决方案的时间复杂度是最优的，即不能进一步降低这个问题的时间复杂度？
我为此 problem.n 给出了一个 nlogn+(n+m) 算法解决方案，m 是给定数组的大小，n>m.I 无法回答 question.Can 的第二部分有人帮助我？
在仅比较模型中，本质上需要排序。考虑一个选择输入的对手，在两个数组的排序顺序中，元素在输入数组之间交替。对于每个元素，算法必须 "prove" 它小于其他数组的某些元素并大于所有其他元素。由于严格交错，此信息加起来就是所有元素的总顺序，这会产生一个 Omega(n log n) 下界。
您可以在时间复杂度上做到这一点 n + m 您可以创建一个 HashSet 的时间复杂度 n，然后对另一个数组中的每个元素执行一个包含。即时间复杂度(O(1)*m)=m。总共 n+m。
你可以用反证法证明这一点。比如，你假设与你认为的相反，然后从逻辑上证明它一定是不可能的，因此你的假设是错误的。如果你的假设选择正确，那么否定它就证明了你原来的观点。
假设：假设有一个时间复杂度低于m+n的算法，可以找到两个数组中的所有公共元素。
这意味着至少有一个元素您没有检查。该元素可能是常见的，也可能不是。不检查就不知道。所以这个算法并不能保证你找到所有共同的元素，这与原来的假设相矛盾。因此，没有比 n+m 更小的算法来寻找共同元素。
这是我求职面试中的一个问题。
你如何找到两个数组中的共同元素？你如何证明这个解决方案的时间复杂度是最优的，即不能进一步降低这个问题的时间复杂度？
我为此 problem.n 给出了一个 nlogn+(n+m) 算法解决方案，m 是给定数组的大小，n>m.I 无法回答 question.Can 的第二部分有人帮助我？
在仅比较模型中，本质上需要排序。考虑一个选择输入的对手，在两个数组的排序顺序中，元素在输入数组之间交替。对于每个元素，算法必须 "prove" 它小于其他数组的某些元素并大于所有其他元素。由于严格交错，此信息加起来就是所有元素的总顺序，这会产生一个 Omega(n log n) 下界。
您可以在时间复杂度上做到这一点 n + m 您可以创建一个 HashSet 的时间复杂度 n，然后对另一个数组中的每个元素执行一个包含。即时间复杂度(O(1)*m)=m。总共 n+m。
你可以用反证法证明这一点。比如，你假设与你认为的相反，然后从逻辑上证明它一定是不可能的，因此你的假设是错误的。如果你的假设选择正确，那么否定它就证明了你原来的观点。
假设：假设有一个时间复杂度低于m+n的算法，可以找到两个数组中的所有公共元素。
这意味着至少有一个元素您没有检查。该元素可能是常见的，也可能不是。不检查就不知道。所以这个算法并不能保证你找到所有共同的元素，这与原来的假设相矛盾。因此，没有比 n+m 更小的算法来寻找共同元素。