（算法）发现如果两个未排序数组在O（n）时间排序没有任何共同的元素？ [英] (Algorithm) Find if two unsorted arrays have any common elements in O(n) time without sorting?

问题描述

我们有两个未排序阵列和每个阵列具有n的长度。这些阵列包含在0-N ¹⁰⁰ 的范围内随机整数。如何找到，如果这两个数组在O（N）/线性时间任何共同的元素？排序是不允许的。

We have two unsorted arrays and each array has a length of n. These arrays contain random integers in the range of 0-n¹⁰⁰. How to find if these two arrays have any common elements in O(n)/linear time? Sorting is not allowed.

推荐答案

您还没有定义的计算模型。假设你只能读取O（1）位在O（1）时间（什么都将是计算一个颇为奇特的模型），就不可能有算法解决O（n）的最坏情况下的时间复杂度的问题。

You have not defined the model of computation. Assuming you can only read O(1) bits in O(1) time (anything else would be a rather exotic model of computation), there can be no algorithm solving the problem in O(n) worst case time complexity.

证明素描： 在输入每个数字需要O（的log（n ^ 100））= O（100日志N）= O（log n）的位。在整个输入，因此为O（n log n）的位，不能读O（n）时间。因此，任何O（n）的算法无法读取整个输入，并且如果这些位关系，因此还没有反应过来。

Proof Sketch: Each number in the input takes O(log(n ^ 100)) = O(100 log n) = O(log n) bits. The entire input therefore O(n log n) bits, which can not be read in O(n) time. Any O(n) algorithm can therefore not read the entire input, and hence not react if these bits matter.

这篇关于（算法）发现如果两个未排序数组在O（n）时间排序没有任何共同的元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！