PAA 2007.1 - Projeto 1 - Mochila Fracionária

Definição do Problema

Dado um conjunto de $n$ objetos (ou items) e uma mochila, para cada objeto $i = 1, 2 \cdots n$ é dado um peso positivo $w_i$ e um valor também positivo $v_i$. A mochila só pode carregar um peso que não exceda sua capacidade $W$. O problema da mochila consiste em determinar o conjunto de objetos a serem carregados na mochila de forma a maximizar o valor transportado, respeitando a restrição de capacidade da mesma. O problema da mochila fracionária é uma variação deste problema onde é permitido carregar frações dos objetos, ou seja, para cada objeto $i$ podemos colocar na mochila uma fração $0 \leq x_i \leq 1$ do mesmo. No caso da mochila fracionária cada objeto na mochila contribui com $x_i*w_i$ para o peso total transportado e $x_i*v_i$ para o valor total transportado. Assim o problema pode ser enunciado da seguinte forma:

maximizar $\sum_{i=1}^{n} x_i v_i$, sujeito a $\sum_{i=1}^{n} x_i w_i \leq W$

onde $v_i > 0$, $w_i > 0$ e $0 \leq x_i \leq 1$ para $i = 1, 2 \cdots n$. Os valores de $v_i$ e $w_i$ bem como o $W$ fazem parte da instância do problema, assim o que queremos determinar são os valores $x_i$ de cada objeto, ou seja, a fração de cada um a ser transportada na mochila.

Algoritmo 1 $O(n*log(n))$

Descrição

Se $\sum_{i=1}^{n} w_i \leq W$ então podemos simplesmente colocar todos os objetos de forma completa na mochila e então teremos a solução ótima sendo $x_i = 1$ para $i=1,2 \cdots n$. Já quando $\sum_{i=1}^{n} w_i > W$ a solução não pode ser determinada de forma direta, temos que encontrar um critério de escolha das frações dos objetos de forma que o valor transportado seja o maior possível. Fica claro neste caso que a solução ótima deverá ocupar toda a capacidade da mochila, ou seja, $\sum_{i=1}^{n} x_i w_i = W$ para $i=1,2 \cdots n$, pois caso contrário poderíamos adicionar uma fração de qualquer objeto que ainda não está na mochila de forma completar capacidade da mesma aumentando também o valor transportado.

Como queremos maximizar o valor transportado na mochila temos que fazer com que cada unidade, das $W$ disponíveis para transporte na mochila, contribua o máximo possível para o valor total. Sabendo que cada unidade de um objeto $i$ tem valor $v_i/w_i$, podemos desenvolver um algoritmo que sucessivamente escolha para colocar na mochila a máxima fração possível (respeitando a capacidade da mochila) do objeto disponível cuja contribuição para o valor total por unidade de peso seja a maior possível. Para implementar esta idéia podemos inicialmente ordenar os objetos de forma decrescente de $v_i/w_i$, e então ir colocando-os na mochila nesta ordem até que o peso do objeto considerado supere a capacidade disponível na mochila, neste caso é colocado na mesma apenas a fração do objeto que completa a sua capacidade $W$, terminando então o algoritmo. O código em C++ a seguir implementa o algoritmo:

// Recebe como parametros o numero de objetos n, 
// o array de objetos com seus respectivos pesos e valores, 
// e a capacidade W da mochila
double mochilaFracNlogN(int n, Object * obj, int W){
    double weight = 0.0; // Peso armazenado na mochila
    double total = 0.0; // Valor total armazenado na mochila
    int i;
 
    // Ordena os objetos com relacao a razao entre valor/peso
    // Complexidade O(n*log(n))
    qsort(obj, n, sizeof(Object), ratioCmp);
 
    // Coloca o maior numero de objetos de forma completa na mochila,
    // em ordem de razao valor/peso => Complexidade O(n)
    for(i=0; i<n; i++){
        // Case nao seja possivel colocar o objeto atual na mochila, 
        // entao sai do laco
        if(obj[i].weight + weight > W) break; 
 
        obj[i].frac = 1.0; // Coloca todo o objeto i na mochila
        total += obj[i].value; // Atualiza o valor total na mochila
        weight += obj[i].weight; // Atualiza o peso total na mochila
    }
 
    // Se nem todos os objetos couberam na mochila,
    // coloca apenas uma fracao do melhor objeto, em termos de valor/peso, 
    //ainda nao considerado
    if(i < n){
         // Coloca apenas a fracao possivel do objeto i na mochila
        obj[i].frac = (W - weight)/(double)obj[i].weight;
        // Atualiza o valor total da mochila
        total += ((double) obj[i].value) * obj[i].frac; 
    }
 
    // retorna o valor total armazenado na mochila
    return total;
}

Análise da Complexidade

O algoritmo consiste de dois passos principais a ordenação do array de objetos e a posterior iteração sobre o mesmo. O primeiro passo toma tempo $O(n*log(n))$ já que é feita uma ordenação em um array de $n$ elementos utilizando o algoritmo de ordenação quicksort. O segundo passo toma tempo $O(n)$, já que a iteração é feita no número $n$ de objetos. Assim a complexidade geral do algoritmo será $O(n*log(n) + n) = O(n*log(n))$.

Corretude

O que o algoritmo faz é selecionar os objetos em ordem decrescente de $v_i/$w_i$ até preencher toda a mochila. Queremos provar que esta estratégia produz uma solução ótima para o problema da mochila fracionária.

Suponha sem perda de generalidade que os objetos disponíveis são numerados em ordem decrescente de valor por unidade de peso, isto é:

$v_1/w_1 \ge v_2/w_2 \ge \cdots \ge v_n/w_n$

Considere $X = (x_1, x_2, \cdots, x_n)$ a solução produzida pelo algoritmo. Se todos os $x_i$ são iguais a 1, a solução é claramente ótima. Caso contrário, seja $j$ o menor índice cujo $x_j < 1$. Observando a forma como o algoritmo trabalha fica claro que $x_i = 1$ quando $i < j$, e que $x_i = 0$ quando $i > j$, e ainda $\sum_{i=1}^{n} x_i w_i = W$. Agora considere o valor da solução $X$ como sendo $V(X) = \sum_{i=1}^{n} x_i v_i$.

Agora considere $Y = (y_1, y_2, \cdots, y_n)$ qualquer outra solução viável. Como $Y$ é viável então $\sum_{i=1}^{n} y_i w_i \leq W$, com este fato notamos também que $\sum_{i=1}^{n} (x_i - y_i) w_i \ge 0$. Considere o valor da solução $Y$ como sendo $V(Y) = \sum_{i=1}^{n} y_i v_i$, assim temos

$V(X) - V(Y) = \sum_{i=1}^{n} (x_i - y_i) v_i = \sum_{i=1}^{n} (x_i - y_i) w_i \frac{v_i}{w_i}$

Quando $i < j$, $x_i = 1$ então $x_i - y_i$ é positivo ou zero, enquanto $v_i/w_i \ge v_j/w_j$, já quando $i > j$, $x_i = 0$ e então $x_i - y_i$ é negativo ou zero, enquanto $v_i/w_i \le v_j/w_j$, e claro quando $i = j$, $v_i/w_i = v_j/w_j$. Dessa forma para todo $i = 1, 2 \cdots n$ temos que $(x_i - y_i)(v_i/w_i) \ge (x_i - y_i)(v_j/w_j)$. Então podemos concluir que

$V(X) - V(Y) \ge (v_j/w_j) \sum_{i=1}^{n}(x_i - y_i) w_i \ge 0$

Assim provamos que não existe solução viável que possua valor estritamente maior que o valor $V(X)$ da solução encontrada pelo algoritmo, logo $X$ é uma solução ótima para o problema da mochila fracionária.

Algoritmo 2 $O(n)$

Descrição e Corretude

Analisando a prova de corretude do algoritmo anterior podemos perceber que a ordem relativa entre os objetos $i < j$ e entre os objetos $i > j$ não é relevante para a prova, assim podemos nos aproveitar de alguma forma deste fato para desenvolver um algoritmo que não necessite ordenar inicialmente os objetos, o que seria bastante proveitoso já que o gargalo do algoritmo anterior é justamente a ordenação. Apesar da ordem relativa entre os objetos $i < j$ e entre os objetos $i > j$ não ser importante, outras propriedades são essenciais para a corretude do algoritmo, sendo a principal delas o respeito ao critério guloso de escolha dos objetos que possuem maior valor por unidade de peso. Baseado no algoritmo anterior e em sua prova de corretude, a seguir identificamos um conjunto de propriedades, que não necessitam da ordenação prévia dos objetos, e que se satisfeitas por uma determinada solução implicam que a mesma seja ótima. A partir destas propriedades, descrevemos um algoritmo de complexidade $O(n)$ para encontrar soluções que respeitam estas propriedades e que portanto também são ótimas.

Relembrando a definição de $j$ na prova anterior, temos $j$ como sendo o menor índice em que $x_j < 1$, devido ao fato de que a inclusão completa do objeto $j$ extrapola a capacidade da mochila, ou seja, $\sum_{i=1}^{j} w_i> W$. Além disto, como $x_i = 1$ para os objetos $i < j$, pelo critério guloso (de seleção dos melhores objetos em termos de valor por unidade de peso) é necessário que $v_i/w_i \ge v_j/w_j$, assim como também é necessário que a soma dos pesos dos mesmos não extrapole a capacidade da mochila, ou seja, $\sum_{i=1}^{j-1} w_i \le W$. Também pelo critério guloso, explicado anteriormente, é necessário que o valor por unidade de peso do elemento $j$ seja o maior possível, ou seja, $v_i/w_i \le v_j/w_j$ para $i > j$. Estamos considerando aqui que a soma dos pesos dos objetos é superior a capacidade da mochila, pois caso contrário o problema seria resolvido trivialmente incluindo todos os objetos na mochila. Assim listando as propriedades essenciais temos:

  1. $v_i/w_i \ge v_j/w_j$ para $i < j$.
  2. $v_i/w_i \le v_j/w_j$ para $i > j$.
  3. $\sum_{i=1}^{j} w_i > W$.
  4. $\sum_{i=1}^{j-1} w_i \le W$.
  5. $x_i = 1$ para $i < j$.
  6. $x_i = 0$ para $i > j$.
  7. $\sum_{i=1}^{n}x_i w_i = W$.

Uma solução que obedece estas propriedades é claramente ótima, para verificar isto basta analisar a prova da corretude do algoritmo anterior, verificando que se substituirmos a parte que considera os elementos ordenados (de forma decrescente de valor por unidade de peso) pela consideração de que eles estão apenas particionados da seguinte forma $v_a/w_a \ge v_j/w_j \ge v_b/w_b$, onde $a = 1 \cdots j-1$ e $b = j+1 \cdots n$ (propriedades 1 e 2), a prova ainda será válida, já que todas as propriedades necessárias na sequência da mesma são satisfeitas pelas propriedades de 1 a 7. Assim nosso problema passa a ser encontrar um particionamento dos objetos do problema, sendo o pivô o objeto de índice $j$ e a relação de particionamento o valor por unidade de peso, que obedeça as propriedades de 1 a 4. Com um particionamento com esta característica é fácil determinar uma solução que satisfaça também as propriedades de 5 a 7, basta tornar $x_i = 1$ para $i < j$, $x_i = 0$ para $i > j$ e $x_j = (W - \sum_{i=1}^{j-1} w_i)/w_j$. A partir deste fato podemos detalhar o procedimento principal de um algoritmo que usa a idéia de encontrar este particionamento e partir dele montar a solução para o problema, a seguir este procedimento é mostrado em uma implementação em C++:

// Recebe como parametros o numero de objetos n, 
// o array de objetos com seus respectivos pesos e valores, 
// a soma dos pesos destes objetos
// e a capacidade W da mochila
double mochilaFracN(int n, Object * obj, int SUM_WEIGHT, int W){
    int k; // Indice do pivo do particionamento do vetor
    // Sendo a soma dos pesos dos objetos menor que a capacidade da mochila,
    // entao todos serao incluidos na mesma, 
    // para isto basta tornar k como sendo a ultima posicao do vetor
    if(SUM_WEIGHT <= W)
        k = n - 1;    
    // Caso contrario particionar o vetor encontrando o pivo k,
    // que obedece as propriedades explanadas
    else
        k = partitionAndFindK(obj, 0, n, W);
    double totalVal = 0.0; // Valor total armazenado na mochila
    int totalW = 0; // Acumulador dos pesos dos objetos armazenados
    // Colocar todos os objetos ateh a posicao k de forma completa
    for(int i=0; i < k; i++){
        obj[i].frac = 1.0;
        totalVal += obj[i].value;
        totalW += obj[i].weight;
    }
    // Coloca a maxima fracao possivel do objeto de posicao k na mochila
    obj[k].frac = min(1.0, double(W - totalW)/double(obj[k].weight));
    totalVal += obj[k].frac * obj[k].value; 
    // Retorna o valor total dos objetos armazenados na mochila
    return totalVal;            
}

A chave do algoritmo está no procedimento partitionAndFindK, ele é o responsável por realizar o particionamento dos objetos em torno de um pivô no qual as propriedades citadas são satisfeitas. A idéia por trás do procedimento é analisar recursivamente, de forma recorrente, diferentes particionamentos em torno de objetos candidatos até que um deles resulte em uma partição com as propriedades desejadas. A cada chamada do procedimento um pivô $k$ é selecionado, e então é feito o particionamento em torno dele, assim o vetor de objetos terá a propriedade $v_a/w_a \ge v_k/w_k \ge v_b/w_b$, onde $a = 1 \cdots k-1$ e $b = k+1 \cdots n$, ou seja, as propriedades 1 e 2 são satisfeitas para $j = k$. Após isto, é verificado se as propriedades 3 e 4 também são satisfeitas para $j = k$, caso sejam, então este particionamento pode ser utilizado para construção da solução e então o procedimento retorna. Caso contrário, apenas uma das propriedades é violada por vez. A seguir são detalhadas as ações do procedimento em cada caso de violação.

Quando a propriedade $\sum_{i=1}^{k} w_i > W$ é violada, significa que a mochila suporta um número maior de objetos que os do intervalo de $1$ a $k$, assim temos que usar um outro objeto $u$ como pivô de forma que após o particionamento $\sum_{i=1}^{u} w_i > W$. Sabemos porém que $u$ só pode estar na partição $k+1$ a $n$, pois apenas usando objetos neste intervalo como pivôs é que será possível aumentar a soma dos pesos dos objetos na partição inicial. Assim o procedimento é chamado recursivamente para buscar o pivô do particionamento adequado nos objetos no intervalo de $k+1$ a $n$. Um fato interessante que podemos notar, nesta chamada recursiva, é que os objetos de $1$ a $k$ farão parte da partição inicial de qualquer particionamento que use um objeto no intervalo de $k+1$ a $n$ como pivô, pois sabemos que $v_a/w_a \ge v_b/w_b$, para $a = 1 \cdots k$ e $b = k+1 \cdots n$. Assim o particionamento na chamada recursiva pode ser feito apenas entre os objetos de $k+1$ a $n$, já que os outros objetos já estão na partição correta, devemos apenas nos preocupar em fazer os testes subsequentes levando em conta não só a soma dos peso dos objetos da partição inicial resultante, mas também a soma dos pesos dos objetos de $1$ a $k$. Esta preocupação é facilmente atendida subtraindo a soma dos pesos dos objetos de $1$ a $k$ da capacidade da mochila no momento da chamada recursiva, isto é o equivalente a considerar que estes objetos serão armazenados na mochila na solução, o que é claramente verdade pois sabemos que eles estão na partição inicial da solução o que implica em $x_i = 1$ para $i = 1 \cdots k$ .

De forma semelhante quando a propriedade $\sum_{i=1}^{k-1} w_i \le W$ é violada, significa que a mochila não suporta todos os objetos do intervalo de $1$ a $k$, assim temos que usar um outro objeto $u$ como pivô de forma que após o particionamento $\sum_{i=1}^{u-1} w_i \le W$. Sabemos porém que $u$ só pode estar na partição $1$ a $k-1$, pois apenas usando objetos neste intervalo como pivôs é que será possível diminuir a soma dos pesos dos objetos na partição inicial. Assim o procedimento é chamado recursivamente para buscar o pivô do particionamento nos objetos no intervalo de $1$ a $k-1$. Novamente podemos notar que os objetos de $k$ a $n$ farão parte da partição final de qualquer particionamento que use um objeto no intervalo de $1$ a $k-1$ como pivô, pois sabemos que $v_a/w_a \ge v_b/w_b$, para $a = 1 \cdots k-1$ e $b = k \cdots n$. Assim o particionamento na chamada recursiva pode ser feito apenas entre os objetos de $1$ a $k-1$, já que os outros objetos já estão na partição correta.

A seguir é mostrada a implementação do procedimento partitionAndFindK em C++:

// Recebe como parametros o array de objetos, 
// o intervalo do array onde o pivo serah procurado (ini, fim)
// e a capacidade atual da mochila 
int partitionAndFindK(Object * obj, int ini, int fim, int W){
    // Seleciona o pivo entre ini e fim que ira particionar o vetor 
    int pivot = select(obj, ini, fim);
    // Particiona o vetor com o pivo selecionado,
    // armazenando em sumW a soma dos pesos dos objetos da particao inicial,
    // considerando tambem na soma o peso do pivot
    int sumW = partition(obj, ini, fim, pivot); 
    // Se o pivot do particionamento satisfaz as propriedades 3 e 4, 
    // entao o algoritmo acaba e retorna o mesmo
    if(sumW >= W && sumW - obj[pivot].weight <= W)
        return pivot;
    // Se o pivo nao satisfaz a propriedade 3, 
    // entao assuma que os objetos da particao inicial serao armazenados,
    // e assim particione e procure o pivo adequado na particao final
    else if(sumW < W)
        return partitionAndFindK(obj, pivot + 1, fim, W - sumW);
    // Se o pivo nao satisfaz a proposicao 4, 
    // entao particione e procure o pivo adequado apenas na particao inicial
    return partitionAndFindK(obj, ini, pivot-1, W);                
}

Podemos notar, analisando o algoritmo, que a cada chamada recursiva o número de objetos considerados para resolução do problema diminui por um certo fator, tratando-se portanto de um algoritmo recorrente. Este fator de redução está intimamente ligado ao particionamento realizado, já que cada chamada recursiva limita o algoritmo a tratar apenas os objetos de uma das partições resultantes. Quanto menor for o tamanho da partição, para qual a chamada recursiva for feita, melhor será o desempenho do algoritmo. Como o tamanho de cada partição é dependente do pivô escolhido, então a chave para o desempenho do algoritmo é a escolha apropriada de um pivô que divida o vetor em partições de tamanho equivalente, pois assim teremos a garantia de que a chamada recursiva para qualquer uma das partições diminuirá o problema por um fator significativo. No algoritmo exibido anteriormente o procedimento select é o responsável pela escolha apropriada do pivô. A seguir o procedimento é descrito.

O procedimento select tenta estimar a mediana (com relação ao valor por unidade de peso) do vetor de objetos, a mediana é o objeto que particiona o vetor exatamente ao meio. A cada iteração do procedimento um conjunto de objetos candidatos a serem selecionados é considerado. Este conjunto é inicialmente dividido em partições de tamanho 5, então de cada uma é selecionada apenas a mediana para a próxima iteração. Como as partições tem tamanho fixo podemos simplesmente ordena-las, o que não afeta a complexidade assintótica, e selecionar o elemento do meio como a mediana. Assim quando apenas um elemento for selecionado, ele será retornado pelo procedimento como o pivô escolhido para o particionamento. Na análise da complexidade do algoritmo mostraremos que este método consegue selecionar um pivô que divide o vetor em partições de tamanho proporcional ao tamanho do mesmo, o que é suficiente para provar que a complexidade total do algoritmo é $O(n)$. A seguir é apresentado o código em C++ que implementa o procedimento select:

int select(Object * obj, int ini, int fim){
    // vetor que guarda os candidatos a serem selecionados como pivo 
    int cand[MAXN]; 
 
    int ncand = fim - ini; // numero de candidatos
 
    // Cria inicialmente a lista de candidatos a serem selecionados
    for(int i=0; i < ncand; i++)
        cand[i] = ini + i;
 
    // Divide os candidatos em grupos de tamanho 5,
    // selecionando a mediana de cada grupo como candidato
    // para a proxima iteracao, continuando ateh que reste apenas um 
    do{
        int storeind = 0;
        // Itera sobre os grupos de candidatos,
        // selecionando a mediana de cada um
        for(int i=0; i < ncand; i+=BUCKSIZE){
            // Determina a posicao de inicio e fim de um grupo
            int posini = i, posfim = i + min(5, ncand - i);
            // Ordena o grupo em termos de razao valor/peso
            sort(cand + posini, cand + posfim, ratioCmp);
            // Seleciona a mediana do grupo
            cand[storeind++] = cand[(posini + posfim)/2]; 
        }    
        ncand = storeind;
    }while(ncand > 1);
 
    // Retorna o objeto selecionado para pivo do particionamento    
    return cand[0];
}

Análise da Complexidade

A complexidade do algoritmo, analisando o procedimento principal, é a soma da complexidade do partitionAndFindK com a complexidade da etapa que monta a solução. Esta última tem complexidade de pior caso $O(n)$, pois apenas itera sobre no máximo todos os $n$ objetos da instância. Já a complexidade do partitionAndFindK pode ser analisada a partir da equação de recorrência do tempo de execução do mesmo. Esta equação nada mais é que a soma das complexidades dos passos executados no algoritmo. No partitionAndFindK é feita uma chamada ao procedimento select, outra ao procedimento partition e uma chamada recursiva recorrente. Assim a equação de recorrência do tempo de execução do partitionAndFindK pode ser expressa como T(n) = T(m) + (complexidade do select) + (complexidade do partition), onde m < n. Tanto a complexidade do select quanto a do partition são funções de $n$, onde o $n$ neste caso representa o tamanho da instância a ser resolvida na chamada do procedimento, o que portanto não necessariamente representa o tamanho total da instância. Toda a análise em diante usa o $n$ com esta conotação.

O procedimento partition é o responsável pelo particionamento do vetor. Este particionamento é feito de forma semelhante ao realizado no algoritmo de ordenação quicksort, a única diferença é que a comparação entre os elementos é feita em relação ao valor por unidade de peso dos mesmos. Assim a complexidade do partition é a mesma do particionamento do quicksort, sendo portanto $O(n)$.

O procedimento select consiste de duas etapas, na primeira é montado em $O(n)$ um vetor inicial de candidatos, e na segunda apenas parte dos candidatos são selecionados de forma recorrente até sobrar apenas um. A segunda parte inicia particionando o vetor de candidatos em partições de tamanho 5, e posteriormente selecionando apenas a mediana de cada uma como candidato para a próxima iteração. A seleção da mediana de cada partição é feita em $O(1)$, já que para isto é feita uma ordenação de um vetor de tamanho fixo e a seleção do objeto central do mesmo. No total a seleção de todas as medianas tem complexidade $O(n)$. Após esta etapa, a iteração posterior corresponderá a uma chamada recursiva ao problema de seleção de medianas em um vetor com um quinto do tamanho do vetor inicial. Assim, podemos representar o tempo de execução da segunda parte do select pela equação de recorrência $T(n) = O(1)$, quando n = 1, e $T(n) = T(n/5) + O(n)$, quando $n > 1$. Neste caso, pelo teorema mestre, a complexidade total da recorrência será $O(n)$, e portanto a complexidade total do select também será $O(n)$.

A equação de recorrência do tempo de execução do partitionAndFindK é então $T(n) = O(1)$ para $n = 1$ e $T(n) = T(m) + O(n)$ para $n > 1$, onde $m<n$. O valor de $m$ representa o tamanho da partição para qual a chamada recursiva será feita. Este valor depende da escolha do pivô feita pelo procedimento select. Analisaremos então o funcionamento do select para tentar estimar o valor de $m$ em função de $n$ no pior caso.

Para estimar o valor de $m$, no pior caso, supomos, sem perda de generalidade, que o número de objetos é divisível por 5, a partir disto estimamos o número de objetos maiores (em termos de valor por unidade de peso) que o objeto pivô $x$ selecionado pelo procedimento select. Sabendo que na parte inicial são selecionadas as medianas de cada partição de tamanho 5, temos que no final do procedimento pelo menos metade destas medianas é maior ou igual a mediana das medianas $x$. Portanto, pelo menos metade das $n/5$ partições contribui com 3 objetos maiores que $x$, assim o o tamanho da partição final, resultante do particionamento do vetor de objetos utilizando como pivô o $x$, pode ser estimado como $3*(1/2*n/5) = 3n/10$, então neste caso a partição inicial deste particionamento terá $7n/10$ objetos. Sendo assim o $m$, no pior caso, pode ser estimado como sendo $m = 7n/10$.

Sabendo o valor de $m$, então o caso geral da equação de recorrência do tempo de execução do partitionAndFindK pode ser representado da seguinte forma $T(n) = T(7n/10) + O(n) = T(n/(10/7)) + O(n)$ para $n > 1$. Assim pelo teorema mestre a complexidade do $T(n)$, e portanto do partitionAndFindK, é $O(n)$. Com isso concluímos que a complexidade geral do algoritmo apresentado é também $O(n)$.

Resultados

Os algoritmos foram executados em um conjunto de instâncias que variam de 50 a aproxidamente 100000 objetos. Para cada instância os algoritmos foram executados repetidamente até que o tempo total gasto ultrapassasse 5 segundos, então o tempo médio de execução de cada algoritmo foi calculado como o tempo total gasto dividido pelo número total de execuções. A seguir é mostrada uma tabela que exibe o tempo médio de execução de cada algoritmo nas instâncias testadas, bem como o valor da solução obtida pelos mesmos. Logo após é apresentado um gráfico comparativo dos tempos médios de execução dos algoritmos.

Instância Tamanho Valor da Solução TM(s) Algoritmo 1 TM(s) Algoritmo 2
m50.in 50 455.33 0.000018 0.000028
m58.in 58 646.00 0.000022 0.000002
m67.in 67 1562.00 0.000027 0.000005
m78.in 78 1076.00 0.000022 0.000001
m91.in 91 1293.00 0.000040 0.000003
m106.in 106 1725.00 0.000048 0.000003
m124.in 124 3274.00 0.000057 0.000004
m145.in 145 2966.00 0.000049 0.000004
m169.in 169 3272.00 0.000090 0.000005
m197.in 197 4313.00 0.000100 0.000004
m230.in 230 8113.00 0.000128 0.000006
m269.in 269 6770.00 0.000102 0.000007
m314.in 314 8485.00 0.000180 0.000009
m367.in 367 11029.00 0.000217 0.000011
m429.in 429 18886.00 0.000258 0.000011
m501.in 501 18225.00 0.000185 0.000013
m586.in 586 23862.00 0.000370 0.000016
m685.in 685 29748.00 0.000466 0.000017
m801.in 801 46388.00 0.000540 0.000020
m937.in 937 48627.00 0.000402 0.000023
m1096.in 1096 63723.00 0.000776 0.000024
m1282.in 1282 80086.00 0.000946 0.000030
m1499.in 1499 116121.00 0.001094 0.000039
m1753.in 1753 131250.00 0.000865 0.000044
m2051.in 2051 167865.00 0.001609 0.000050
m2399.in 2399 216249.00 0.001915 0.000057
m2806.in 2806 304764.00 0.002213 0.000068
m3283.in 3283 354401.00 0.001793 0.000081
m3841.in 3841 456215.00 0.003143 0.000092
m4493.in 4493 578835.00 0.003726 0.000108
m5256.in 5256 805600.00 0.004575 0.000125
m6149.in 6149 955114.00 0.003718 0.000149
m7194.in 7194 1240551.00 0.006511 0.000175
m8416.in 8416 1592267.00 0.007723 0.000205
m9846.in 9846 2157401.00 0.008959 0.000255
m11519.in 11519 2657385.00 0.007693 0.000308
m13477.in 13477 3379083.00 0.012854 0.000365
m15768.in 15768 4344096.00 0.015386 0.000508
m18448.in 18448 5751239.00 0.018227 0.000704
m21584.in 21584 7164528.00 0.016001 0.000994
m25253.in 25253 9172388.00 0.026106 0.001358
m29546.in 29546 11864606.00 0.031749 0.001736
m34568.in 34568 15593477.00 0.036146 0.002181
m40444.in 40444 19668481.00 0.033002 0.002588
m47319.in 47319 25304273.00 0.053140 0.003129
m55363.in 55363 32633200.00 0.064466 0.003679
m64774.in 64774 42518422.00 0.070540 0.004344
m75785.in 75785 53890371.00 0.067151 0.004974
m88668.in 88668 69476973.00 0.104088 0.005689
m103741.in 103741 32713.33 0.123910 0.076671

TM(s) - Tempo médio de execução em segundos.

grafico

Analisando os resultados apresentados, podemos perceber que o algoritmo 2 (complexidade $O(n)$) apresenta tempos médios de execução inferiores aos tempos do algoritmo 1 (complexidade $O(n*log(n))$), além disto a taxa de crescimento dos valores de tempo médio do algoritmo 1 é superior a do algoritmo 2. Estas constatações apenas comprovam o que a análise da complexidade assintótica previa, ou seja, que o algoritmo de complexidade $O(n)$ teria um desempenho melhor que o algoritmo de complexidade $O(n*log(n))$ para todas as instâncias a partir de um tamanho $n$ suficientemente grande. Portanto os resultados práticos estão de acordo com a análise teórica apresentada, validando então o trabalho de desenvolvimento e estudo dos algoritmos apresentados.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.