算法导论(第三版)Exercises2.3(归并排序、二分查找、计算集合中是否有和为X的2个元素)

2.3-1:

3 9 26 38 41 49 52 59

3 26 41 52   9 38 49 57

3 41   52 26   38 57   9 49

3   41  52  26  38  57  9  49

2.3-2:(归并排序)

void mergeSort(int a[], int l, int r)

{

    int m;

    if(l < r)

    {

        m = (l + r) / ;

        mergeSort(a, l, m);

        mergeSort(a, m+, r);

        merge(a, l, r, m);

    }

}

void merge(int a[], int l, int r, int p)

{

    int i, j, k;

    int n1 = p - l + ;

    int n2 = r - p;

    int lArray[n1], rArray[n2];

    for(i=; i<n1; i++) lArray[i] = a[l+i];

    for(j=; j<n2; j++) rArray[j] = a[p+j+];

    i = ;

    j = ;

    for(k=l; k<=r; k++)

    {

        if(i < n1 && (j >= n2 || lArray[i] <= rArray[j]))

        {

            a[k] = lArray[i];

            ++i;

        }

        else if(j < n2 && (i >= n1 || rArray[j] < lArray[i]))

        {

            a[k] = rArray[j];

            ++j;

        }

    }

}

2.3-3:

n=2:  Tn=2lg2=2

假设 n=k时等式成立

T_k+1=2(T_k) + 2^k+1=2 * (2^k * k) + 2^k+1=2^k+1(k+1)

2.3-4:

最差情况：

1   n=2;

T_n = T_n-1+n-1;

2.3-5:(二分查找)

int binarySearch(int a[], int v, int n)

{

    int l, r, m;

    l = ;

    r = n - ;

    while(l <= r)

    {

        m = (l + r) / ;

        if(v < a[m]) r = m - ;

        else if(v > a[m]) l = m + ;

        else return m;

    }

    return -;

}

最差情况：

2   n=2;

T_n=T(n/2) + 1      n=2^k;

θ(lgn)

2.3-6:

无法降低运行时间

2.3-7:(参考了网友的答案，做了一点优化，希望大家能提更好的改进建议）

算法：求一个N个数的集合是否含有和为X的2个元素(需要支持c99标准)

bool sumX(int a[], int n, int x)

{

    int length, complement[n];

    mergeSort(a, , n-);

    length = deduplication(a, n);

    xComplement(a, complement, length, x);

    return mergeSearch(a, complement, length);

}

bool mergeSearch(int a[], int b[], int n)

{

    int i, j;

    for(i=, j=n-; i<n && j>= && a[i]!=b[j]; )

        if(a[i] < b[j]) i++;

        else j--;

    return i<n && j>=;

}

void xComplement(int a[], int aComplement[], int n, int x)

{

    int i;

    for(i=; i<n; i++) aComplement[i] = x - a[i];

}

int deduplication(int a[], int n)

{

    int i, tmp[n];

    int j = ;

    for(i=; i<n; i++)

    {

        if(i >  && a[i-] != a[i]) j++;

        tmp[j] = a[i];

    }

    for(i=; i<=j; i++) a[i] = tmp[i];

    return j+;

}

void mergeSort(int a[], int l, int r)

{

    int m;

    if(l < r)

    {

        m = (l + r) / ;

        mergeSort(a, l, m);

        mergeSort(a, m+, r);

        merge(a, l, r, m);

    }

}

void merge(int a[], int l, int r, int m)

{

    int max = ;

    int i, j, k;

    int n1 = m - l + ;

    int n2 = r - m;

    int lArray[n1+], rArray[n2+];

    for(i=; i<n1; i++) lArray[i] = a[l+i];

    for(j=; j<n2; j++) rArray[j] = a[m+j+];

    lArray[n1] = max;

    rArray[n2] = max;

    i = ;

    j = ;

    for(k=l; k<=r; k++)

    {

        if(i < n1 && lArray[i] <= rArray[j])

        {

            a[k] = lArray[i];

            ++i;

        }

        else

        {

            a[k] = rArray[j];

            ++j;

        }

    }

}

θ(nlgn)

算法导论(第三版)Exercises2.3(归并排序、二分查找、计算集合中是否有和为X的2个元素)的相关教程结束。