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 . A recorrência original:

(1)

Hipótese:
Caso base: , correto.
Passo indutivo: assumindo , vamos encontrar :

(2)

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)

2.3-5

O algoritmo é fácil de encontrar. Vamos mostrar, por indução, que a complexidade é . Recorrência:

(4)

Caso base: , correto.
Passo indutivo:

(5)

2.3-6

Não, pois mesmo encontrando o local certo de inserção em , 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, .

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;
}