遍历两个未排序的整数列表的时间复杂度与排序然后遍历列表相比如何？
How does the time complexity of iterating through two unsorted list of integers compare to sorting then iterating through the lists?
这个问题是关于两个算法的时间复杂度。
所以我正在解决一个涉及两个整数列表（未排序）的问题，我想 return 具有 最小绝对值的整数对（每个列表中的一个）差异.
天真的方法是简单地遍历两个列表，并始终跟踪最小的差异，最后 return 产生这种差异的对 - 我相信这会取 O(mn) time，其中 n 和 m 是每个列表的长度；因为我们只是使用 2x for loops.
另一种方法是 sort 两个列表，然后遍历它们整个第二个列表。我相信这将需要 O(nlogn + mlogm) time，其中 n、m 是两个列表的长度。
我在解决方案页面上看到解决方案 2. 更有效，但我不明白为什么？- 如果我上面提到的时间复杂度是正确的，对于解决方案 2. 如果我们通过 mn 还剩下 >0??
让我们稍微简化方程式并假设：n = m
- 第一种情况，复杂度为：n * m = n^2
- 第二种情况，复杂度为：n * log(n) + m * log(m) = 2 * n * log(n)
对于任何现有的 n，你有 2*log(n) < n，即第二个解决方案比第一个快。
我们可以通过示例更好地了解差异。假设我们有 2 个列表，每个列表包含 1 到 100 的 100 项列表。
list1 = [11, 2, 33, 4, 5, 67, ...] = n 项 n 为 100list2 = [8, 90, 1, 23, 45, 7, ...] = m 项 m 为 100
天真的方法
步骤：
- 遍历 list1 的
n 项的每个元素
- 时间复杂度：
n = 100
- 对于上述每次迭代，迭代 list2 的
m 项的每个元素只是为了获得与 list1 的当前项产生最小差异的数字。
- 时间复杂度：
n * m = 100 * 100 = 10,000
总时间复杂度：n * m = 10,000
排序数据方法 1
步骤：
- 排序
list2 生成 [1, 2, 3, 4, 5, ...]
- 时间复杂度：
m * log(m) = 100 * log(100) = 664.4 = ~700
- 遍历 list1 的
n 项的每个元素
- 时间复杂度：
n = 100
- 对于上述每次迭代，对
list2 的已排序项目执行 binary search 以查看 list1 的当前项目最接近的位置。
- 为了进一步解释这一点，假设我们有一个已排序的 8 项列表
[0, 5, 10, 15, 20, 25, 30, 35]
- 如果我们要搜索最接近值的数字是
22，我们不需要遍历整个列表。就像一个dictionary/thesaurus，如果你要找单词“Potato”，你不会从第1页开始浏览字典，你会做的是到中间，如果它低于“P”如“M”则走得更远，但如果更高如“S”则返回，然后重复。
- 所以我们要检查的项目是中间的
15，然后是 25，然后是 20。这 3 项证明了 log(n) = log(8) = 3 的二进制搜索时间复杂度，因为我们每一步都将列表分成两半。
- 一旦我们到达
20，我们可以检查周围的数字，即 [15, 20, 25] 以查看最接近 22 的数字，即 20，因此它是要配对以获得最小差异的数字。这只是一个常量 O(1) 操作。
- 时间复杂度：
n * log(m) = 100 * log(100) = 664.4 = ~700
总时间复杂度：(m * log(m)) + (n * log(m)) = 700 + 700 = 1,400
排序数据方法 2
- 排序
list1 产生 [1, 2, 3, 4, 5, ...]
- 时间复杂度：
n * log(n) = 100 * log(100) = 664.4 = ~700
- 排序
list2 生成 [1, 2, 3, 4, 5, ...]
- 时间复杂度：
m * log(m) = 100 * log(100) = 664.4 = ~700
- 同时遍历
list1 和 list2 以了解哪对会产生最小差异。移动具有较小值的迭代器。这个想法就像两个人通过楼梯向上搬运木头，较低的人将移动更高的人，保持同步并且两个人始终保持彼此最近的距离（否则木头会坠落^_^)。
- 时间复杂度：
n + m = 100 + 100 = 200
总时间复杂度：(n * log(n)) + (m * log(m)) + n + m = (n * log(n)) + (m * log(m)) = 700 + 700 = 1,400
n + m 已删除，因为它们是非主导词
结论
对于 2 个大小为 100 的列表，排序数据方法比原始方法快约 8,600 次迭代。
这个问题是关于两个算法的时间复杂度。
所以我正在解决一个涉及两个整数列表（未排序）的问题，我想 return 具有 最小绝对值的整数对（每个列表中的一个）差异.
天真的方法是简单地遍历两个列表，并始终跟踪最小的差异，最后 return 产生这种差异的对 - 我相信这会取
O(mn) time，其中 n 和 m 是每个列表的长度；因为我们只是使用2x for loops.另一种方法是
sort两个列表，然后遍历它们整个第二个列表。我相信这将需要O(nlogn + mlogm) time，其中 n、m 是两个列表的长度。
我在解决方案页面上看到解决方案 2. 更有效，但我不明白为什么？- 如果我上面提到的时间复杂度是正确的，对于解决方案 2. 如果我们通过 mn 还剩下 >0??
让我们稍微简化方程式并假设：n = m
- 第一种情况，复杂度为：n * m = n^2
- 第二种情况，复杂度为：n * log(n) + m * log(m) = 2 * n * log(n)
对于任何现有的 n，你有 2*log(n) < n，即第二个解决方案比第一个快。
我们可以通过示例更好地了解差异。假设我们有 2 个列表，每个列表包含 1 到 100 的 100 项列表。
list1=[11, 2, 33, 4, 5, 67, ...]=n项n为 100list2=[8, 90, 1, 23, 45, 7, ...]=m项m为 100
天真的方法
步骤：
- 遍历 list1 的
n项的每个元素- 时间复杂度：
n = 100
- 时间复杂度：
- 对于上述每次迭代，迭代 list2 的
m项的每个元素只是为了获得与 list1 的当前项产生最小差异的数字。- 时间复杂度：
n * m = 100 * 100 = 10,000
- 时间复杂度：
总时间复杂度：n * m = 10,000
排序数据方法 1
步骤：
- 排序
list2生成[1, 2, 3, 4, 5, ...]- 时间复杂度：
m * log(m) = 100 * log(100) = 664.4 = ~700
- 时间复杂度：
- 遍历 list1 的
n项的每个元素- 时间复杂度：
n = 100
- 时间复杂度：
- 对于上述每次迭代，对
list2的已排序项目执行 binary search 以查看list1的当前项目最接近的位置。- 为了进一步解释这一点，假设我们有一个已排序的 8 项列表
[0, 5, 10, 15, 20, 25, 30, 35] - 如果我们要搜索最接近值的数字是
22，我们不需要遍历整个列表。就像一个dictionary/thesaurus，如果你要找单词“Potato”，你不会从第1页开始浏览字典，你会做的是到中间，如果它低于“P”如“M”则走得更远，但如果更高如“S”则返回，然后重复。 - 所以我们要检查的项目是中间的
15，然后是25，然后是20。这 3 项证明了log(n) = log(8) = 3的二进制搜索时间复杂度，因为我们每一步都将列表分成两半。 - 一旦我们到达
20，我们可以检查周围的数字，即[15, 20, 25]以查看最接近22的数字，即20，因此它是要配对以获得最小差异的数字。这只是一个常量O(1)操作。 - 时间复杂度：
n * log(m) = 100 * log(100) = 664.4 = ~700
- 为了进一步解释这一点，假设我们有一个已排序的 8 项列表
总时间复杂度：(m * log(m)) + (n * log(m)) = 700 + 700 = 1,400
排序数据方法 2
- 排序
list1产生[1, 2, 3, 4, 5, ...]- 时间复杂度：
n * log(n) = 100 * log(100) = 664.4 = ~700
- 时间复杂度：
- 排序
list2生成[1, 2, 3, 4, 5, ...]- 时间复杂度：
m * log(m) = 100 * log(100) = 664.4 = ~700
- 时间复杂度：
- 同时遍历
list1和list2以了解哪对会产生最小差异。移动具有较小值的迭代器。这个想法就像两个人通过楼梯向上搬运木头，较低的人将移动更高的人，保持同步并且两个人始终保持彼此最近的距离（否则木头会坠落^_^)。- 时间复杂度：
n + m = 100 + 100 = 200
- 时间复杂度：
总时间复杂度：(n * log(n)) + (m * log(m)) + n + m = (n * log(n)) + (m * log(m)) = 700 + 700 = 1,400
n + m已删除，因为它们是非主导词
结论
对于 2 个大小为 100 的列表，排序数据方法比原始方法快约 8,600 次迭代。