检查大小为 N 的 ArrayList 中是否有两个数字的总和为 N
Check if in ArrayList of size N, there are two numbers which their sum is N
我有作业要做。
我必须实现一个算法，该算法必须检查大小为 N 的 ArrayList 中是否至少有两个数字相加，它们的总和为 N。
算法的复杂度必须是 Theta(n log n)。
我已经知道我可以使用 Merge.Sort，或者堆排序，然后我必须用数组列表的每个元素减去数组列表的大小。
问题是：按顺序减去复杂性，仍然是
Theta（n log n）？！？
如果没有，我怎样才能保持这种状态？
使用 MergeSort 对数组进行排序，时间复杂度为 O(n log n)
然后对于数组中的每条记录 r_i 使用二分搜索查找记录 N - r_i，即 O(log n)
合并排序的复杂度为 O(n log n) + n 次二分查找的复杂度为 O(n log n) --> O(n log n)
使用任何排序算法对数组进行排序，最好是具有可接受顺序的算法，例如 mergeSort，它是 (O(nlogn));
然后开始检查数组的第一个和最后一个元素并保留它们的索引，即'start'和'end。
当最后一个元素大于您想要的值时，将索引减一，然后将 'start' 和 'end' 的总和与您想要的值
进行比较
如果大于你想要的值，你将找不到任何两个满足你条件的值，
如果它等于您想要的值，请报告 'start' 和 'end' 元素
如果它小于您想要的值，则增加 'start' 索引
并再次进行比较，
重复直到两个索引相遇。
最终复杂度为：O(n) + O(nlogn) 等于 O(nlogn)
我有作业要做。 我必须实现一个算法，该算法必须检查大小为 N 的 ArrayList 中是否至少有两个数字相加，它们的总和为 N。 算法的复杂度必须是 Theta(n log n)。 我已经知道我可以使用 Merge.Sort，或者堆排序，然后我必须用数组列表的每个元素减去数组列表的大小。 问题是：按顺序减去复杂性，仍然是 Theta（n log n）？！？ 如果没有，我怎样才能保持这种状态？
使用 MergeSort 对数组进行排序，时间复杂度为 O(n log n) 然后对于数组中的每条记录 r_i 使用二分搜索查找记录 N - r_i，即 O(log n)
合并排序的复杂度为 O(n log n) + n 次二分查找的复杂度为 O(n log n) --> O(n log n)
使用任何排序算法对数组进行排序，最好是具有可接受顺序的算法，例如 mergeSort，它是 (O(nlogn));
然后开始检查数组的第一个和最后一个元素并保留它们的索引，即'start'和'end。 当最后一个元素大于您想要的值时，将索引减一，然后将 'start' 和 'end' 的总和与您想要的值
进行比较如果大于你想要的值，你将找不到任何两个满足你条件的值，
如果它等于您想要的值，请报告 'start' 和 'end' 元素
如果它小于您想要的值，则增加 'start' 索引 并再次进行比较，
重复直到两个索引相遇。
最终复杂度为：O(n) + O(nlogn) 等于 O(nlogn)