写一个算法Θ（nlogn） [英] writing an algorithm with Θ(nlogn)

问题描述

我写了这个code为自己（这是不是一个在家工作），我想知道这是正确的？谢谢

随时间Θ（nlogn），它可以提供n个成员的阵列，以确定阵列中是等于x，然后两个元素是否返回那些元件算法

 算法的总和（改编，1，N）：
归并（ARR）
对于I＆LT;  -  1到n
    M＆LT;  - 二分查找（改编，改编[I]，I + 1，N）
返回米，常用3 [I]
//总和算法结束

算法二分查找（改编，改编[I]，P，Q）
J＆其中 -  [P + Q / 2]
如果（ARR [J] +改编[I] = X）
       返回ARR [J]。
否则，如果（I＆LT; j）条
       返回BinarySearch的（改编，改编[I]，P，J-1）
其他
       返回二分查找（改编，改编[I-J]，J + 1，Q）
 //二分查找算法结束
 

解决方案

您的二进制搜索是不正确的。

您应该比不上我与Ĵ，你应该比较总和。此外，它是容易，如果你的二进制搜索 X - 常用3 [I]

 算法二分查找（改编，改编[I]，P，Q）
如果（P = = Q）
    如果（ARR [P] == x  - 改编[I]）
        返回p
    其他
        回报NO_SOLUTION
J＆其中 -  [（P + Q）/ 2] //您忘记括号
如果（ARR [J] = X  - 改编[I]）
       返回ARR [J]。
否则，如果（ARR [J] GT，X  - 改编[I]）//我们数过大，将搜索限制在更小的数字
       返回二分查找（改编，改编[I]，P，J）
其他
       返回BinarySearch的（改编，改编[I]中，J + 1，q）的常用3 // [I]不改变
 

另外，你一直在你的主要功能覆盖 M 。你需要的东西是这样的：

 算法的总和（改编，1，N）：
归并（ARR）
M = NO_SOLUTION
对于I＆LT;  -  1到n  -  1
    如果（米= NO_SOLUTION）
        M＆LT;  - 二分查找（改编，改编[I]，I + 1，N）
    其他
        打破;

如果（米= NO_SOLUTION）
    回报NO_SOLUTION
其他
    返回米，常用3 [I]
 

这可以确保你停下后，你找到了解决办法。你的情况，算法将总是返回 NO_SOLUTION ，因为没有什么组的最后一个元素。此外，您只需要上去 N - 1 出于同样的原因

I have written this code for myself(it is not a home work) I want to know is this correct?thanks

Algorithm with time Θ (nlogn), which can provide an array of n members to determine whether two elements in the array that are equal to x and then return those elements

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

解决方案

Your binary search is not right.

You shouldn't compare i with j, you should compare the sum. Also, it is easier if you binary search for 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

Also, you keep overwriting m in your main function. You need something like this:

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]   

This makes sure you stop after you found a solution. In your case, the algorithm would always return NO_SOLUTION because there's nothing to group the last element with. Also, you only need to go up to n - 1 for the same reason.

这篇关于写一个算法Θ（nlogn）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！