Atividades em Análise de Algoritmos e C

1. Qual é o menor valor inteiro de n tal que um algoritmo cujo tempo de execução é 100n2 funciona mais rápido que um algoritmo cujo tempo de execução é 2n na mesma máquina? Implemente um algoritmo que imprima na tela a resposta correta.

#include 
#include 

int main(){
    int n;
    for(n = 1; n < 20; n++){
        if( (100 * n * n) < pow(2, n) ){
            printf("%s %d\n", "100*n^2 funciona mais rapido apartir de: ", n);
            break;
        }
    }
    return 0;
}

2. Supondo que estamos comparando implementações de ordenação por inserção e por intercalação na mesma máquina. Para entradas de tamanho n, a ordenação por inserção é executada em \(8n^2\) etapas, enquanto a ordenação por intercalação é executada em \(64n log_2 n\) etapas. A partir de qual valor inteiro de n a ordenação por intercalação supera a ordenação por inserção. Implemente um algoritmo que imprima a resposta correta na tela.

#include 
#include 

int main(){
    int n = 1;
    float a = 0, b = 1;
    while(n<50){ a = 8 * n * n; b = 64 * n * log2(n); printf("%f %f \n", a, b ); if(a>b&&n>1){
            printf("O algoritmo de itercalação vale a pena a partir de n = %d", n);
            break;
        }
        n++;
    }
    return 0;
}

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *