Exercícios do Introduction to Algorithms (Cormen) - Cap. 2

2.3-2

#include <iostream>
#include <vector>
#include <algorithm>
 
#define FOR(i,n) for (int i=0;i<n;i++)
#define FORAE(i,a,n) for (int i=a;i<=n;i++)
 
using namespace std;
 
typedef vector<int> vi;
 
void merge(vi &v, int b, int m, int e) {
        int n1 = m-b+1;
        int n2 = e-m;
        vi L(n1), R(n2);
        FOR(i,n1) L[i] = v[b+i];
        FOR(i,n2) R[i] = v[m+i+1];
 
        int i = 0, j = 0, k = b;
        for (; k < e && i < (int)L.size() && j < (int)R.size();k++) {
                if (L[i] < R[j]) {
                        v[k] = L[i];
                        i++;
                } else {
                        v[k] = R[j];
                        j++;
                }
        }
 
        while (i < (int)L.size())
                v[k++] = L[i++];
        while (j < (int)R.size())
                v[k++] = R[j++];
}
 
void mergesort(vi &v, int b, int e) {
        if (b < e) {
                int q = (b+e)/2;
                mergesort(v,b,q);
                mergesort(v,q+1,e);
                merge(v,b,q,e);
        }
}
 
int main(int argc, char **argv) {
        vi teste;
        int n;
        srand(time(0));
 
        cin >> n;
        for (int i=0;i<n;i++) teste.push_back( rand() % (1<<20) );
        mergesort(teste,0,teste.size()-1);
        FOR(i,teste.size()) cout << teste[i] << endl;
        return 0;
}

2.3-3

Vamos assumir que $\log = \log_2$. A recorrência original:

(1)
\begin{eqnarray} T(n) &=& 2, \mbox{ se n = 2 } \\ T(n) &=& 2T(n/2) + n, \mbox{ se } n>2^k \end{eqnarray}

Hipótese: $T(n) = n\log{n}$
Caso base: $T(2) = 2\log{2} = 2$, correto.
Passo indutivo: assumindo $T(n)$, vamos encontrar $T(2n)$:

(2)
\begin{eqnarray} T(2n) & = & 2n\log{2n} \\ & = & 2n(\log{2}+\log{n}) \\ & = & 2n + 2n\log{n} \\ & = & 2(n\log{n}) + 2n \\ & = & 2T(n) + 2n \end{eqnarray}

2.3-4

A recorrência é dada pelo custo de ordenar os n-1 primeiros elementos mais o custo de colocar o elemento na posição correta (tendo que deslocar, no máximo, (n-1) elementos).

(3)
\begin{eqnarray} T(n) &=& 1, \mbox{ se n = 1 } \\ T(n) &=& T(n-1) + (n-1), \mbox{ se } n>1 \end{eqnarray}

2.3-5

O algoritmo é fácil de encontrar. Vamos mostrar, por indução, que a complexidade é $O(\log{n})$. Recorrência:

(4)
\begin{eqnarray} T(n) &=& c1, \mbox{ se n = 1 } \\ T(n) &=& T(n/2) + c2, \mbox{ se } n > 1 \end{eqnarray}

Caso base: $T(1) = \log{1} = c1$, correto.
Passo indutivo:

(5)
\begin{eqnarray} T(2n) & = & \log{2n} \\ & = & \log{2}+\log{n} \\ & = & 1 + \log{n} \\ & = & \log{n} + c2 \\ & = & T(n) + c2 \end{eqnarray}

2.3-6

Não, pois mesmo encontrando o local certo de inserção em $O(\log{n})$, ainda é necessário deslocar todos os elementos (maiores que o elemento a ser inserido) uma posição a direita, o que custa, no pior caso, $O(n)$.

2.3-7

#include <iostream>
#include <vector>
#include <algorithm>
 
#define FOR(i,n) for (int i=0;i<n;i++)
#define FORAE(i,a,n) for (int i=a;i<=n;i++)
#define all(c) (c).begin(),(c).end()
#define sz(c) (int)((c).size())
 
using namespace std;
 
typedef vector<int> vi;
 
int main(int argc, char **argv) {
        vi vetor;
        int n, x;
        srand(time(0));
 
        // numero de elementos do vetor
        cin >> n;
        for (int i=0;i<n;i++) vetor.push_back( rand() % (1<<20) );
 
        // elemento a ser buscado
        cin >> x;
 
        sort(all(vetor)); // ordena
        FOR(i,sz(vetor)) { // N passos
                // busca binaria pelo elemento (x-vetor[i]) - log(n) passos
                if (binary_search(all(vetor),x-vetor[i]))
                        cout << vetor[i] << " + " << x-vetor[i] << " = " << x << endl;
        }
        return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.