用 Θ(nlogn) 编写算法

Question

我自己写了这段代码（这不是家庭作业）我想知道这是正确的吗？感谢

时间为 θ (nlogn) 的算法，它可以提供一个包含 n 个成员的数组来确定数组中的两个元素是否是等于 x 然后返回这些元素

Algorithm Sum(arr,1,n):
MergeSort(arr)
For i<-- 1 to n
    m<-- BinarySearch(arr,arr[i],i+1,n)
return m and arr[i]   
//end of the sum algorithm

Algorithm BinarySearch(arr,arr[i],p,q)
J<--[p+q/2]
If (arr[j]+arr[i]=x)
       Return arr[j]
else if (i<j)
       Return BinarySearch(arr,arr[i],p,j-1)
else 
       Return BinarySearch(arr,arr[i-j],j+1,q)
 // end of BinarySearch algorithm

Answer 1

你的二分查找是不正确的。

您不应该将 i 与 j 进行比较，而应该比较总和。另外，如果您对 x - arr[i] 进行二分搜索，会更容易。

Algorithm BinarySearch(arr,arr[i],p,q)
if (p == q)
    if (arr[p] == x - arr[i])
        return p
    else
        return NO_SOLUTION
j<--[(p+q)/2] // you forgot parentheses
If (arr[j] = x - arr[i]) 
       Return arr[j] 
else if (arr[j] > x - arr[i]) // our number is too big, restrict the search to smaller numbers
       Return BinarySearch(arr,arr[i],p,j)
else 
       Return BinarySearch(arr,arr[i],j+1,q) // arr[i] doesn't change

另外，您不断在主函数中覆盖 m 。你需要这样的东西：

Algorithm Sum(arr,1,n):
MergeSort(arr)
m = NO_SOLUTION
For i<-- 1 to n - 1
    if (m = NO_SOLUTION)
        m<-- BinarySearch(arr,arr[i],i+1,n)
    else
        break;

if (m = NO_SOLUTION)
    return NO_SOLUTION
else
    return m and arr[i]   

这可以确保你在找到解决方案后停止。在您的情况下，算法将始终返回 NO_SOLUTION 因为没有任何内容可以将最后一个元素分组。此外，出于同样的原因，您只需要上升到 n - 1 即可。