TOPIC

Time Limit Exceeded, o que será?

Joseph Sidnei asked 1 year ago

Meu código está dando Time Limit Exceeded no URI, como posso resolver isso?

Fiz utilizando o Insert Sort pois infelizmente ainda não consigo entender métodos de sort mais complexos (por exemplo, Radix, Shell, etc.), então resolvi adaptar o Insert, e também fiz um método parecido com o Bubble para separar os ímpares dos pares.

#include <stdio.h>
#include <stdlib.h>

void insertSortAdaptado (int *v, int n, int contPar, int contImpar) {
    int i, j, k, aux;

    // Ordenar os pares
    for (i = 1; i < contPar; i++) {
        aux = v[i];

        for (j = i - 1; (j >= 0) && (aux < v[j]); j--) {
            v[j + 1] = v[j];
        }

        v[j + 1] = aux;
    }

    // Ordenar os impares
    for (i = contPar + 1; i < n; i++) {
        aux = v[i];

        for (j = i - 1; (j >= contPar) && (aux < v[j]); j--) {
            v[j + 1] = v[j];
        }

        v[j + 1] = aux;
    }

    // Inverter ímpares
    j = n - (contImpar / 2);
    k = 0;

    for (i = contPar; i < j; i++) {
        aux = v[i];
        v[i] = v[n - 1 - k];
        v[n - 1 - k] = aux;
        k++;
    }
}

void sortParImpar(int *v, int n, int contPar) {
    int i, j, aux;

    for (i = n - 1; i >= contPar; i--) {
        for (j = 0; j < i; j++) {
            if (v[j] % 2 != 0) {
                aux = v[j];
                v[j] = v[i];
                v[i] = aux;
            }
        }
    }
}

int main() {
    int i, j, n, aux, contPar = 0, contImpar = 0;

    scanf("%d", &n);

    int v[n];

    for (i = 0; i < n; i++) {
        scanf("%d", &v[i]);

        if (v[i] % 2 == 0) {
            contPar++;
        } else {
            contImpar++;
        }
    }

    sortParImpar(v, n, contPar);
    insertSortAdaptado(v, n, contPar, contImpar);

    for (i = 0; i < n; i++) {
        printf("%d\n", v[i]);
    }

    return 0;
}

Remember not post solutions. Your post may be reviewed by our moderators.

  • Alexandre Gadelha replied 1 year ago

    Analisando o seu código fonte e levando em conta a minha postagem anterior, creio que não seja necessário a inversão dos ímpares, tendo em vista que isso já é possível pela própria ordenação (decrescente) e também a separação entre pares e ímpares nem precisaria, se for levar em conta que teremos dois Vetores diferentes. É só exibir todo o conteúdo do primeiro e depois o conteúdo do segundo.

    Quanto a ordenação, tanto nos pares quanto nos ímpares, por ser do Insertion Sort é complexidade quadrática, enquanto o mesmo acontece na separação dos pares e ímpares com o Bubble Sort. O FOR responsável pela inversão é de complexidade linear e acaba somando aí no total de tempo de execução do algoritmo no pior caso - mesmo que seja pouca coisa.

    Em complexidade linear, quando se N de cada vetor valer 50000, então teremos ainda 50000, mas no caso da complexidade quadrática, teremos 2500000000, ou seja, 2,5 x 10^9 e isso é um problema. Em 10^9 é impossível oferecer uma resposta dentro de 1 segundo e sem contar que isso tá acontecendo 3 vezes!

  • [BCC BAURU] Rodrigo Rossetti replied 1 year ago

    O C já tem implementado uma função qsort(), se você usá-la passa facilmente nesse problema http://www.cplusplus.com/reference/cstdlib/qsort/

  • Alexandre Gadelha replied 1 year ago

    Olá.

    Primeiramente, atente para as entradas do problema e para a entrada principal. O valor N vai até 100000 (ou 10^5). O exercício pede pra que os números pares sejam organizados de forma crescente enquanto os ímpares de forma decrescente. Isso significa dizer que esse vetor irá se explodir em dois e depois serem exibidos. O pior caso tende a ser 50000 números pares e 50000 números ímpares (50000 é 5 x 10^4) ou 1 número par contra 99999 ímpares e vice-versa. Pra manter o balanço, considere-se a primeira opção.

    Isso já dará uma ideia de qual algoritmo utilizar. Geralmente em ordenação existem os de complexidade quadrática [O(n^2)] e os de complexidade linearítmica [O(n log n)]. Pesquisando aqui rapidamente vi que também existem os de complexidade linear [O(n)] mas nunca os utilizei.

    Algoritmos como o Radix Sort e o Counting Sort são lineares em conjunto a uma constante K, que ainda assim são mais eficientes que os tradicionais Bubble Sort, Selection Sort e Insertion Sort. Quick Sort e Shell Sort são linearítmicos e pode ser uma boa escolha pra esse caso.

    Eu resolvi esse problema tanto com Shell Sort quanto com o Quick Sort. Sendo assim, quanto a organização dos dois vetores resultaria em:

    50000 x log10(50000) = 50000 x [log10(5) + log10(10000)] = 50000 x [log10(5) + 4 x log10(10)] = 50000 x (cerca de 4,6989... em dízima) = cerca de 234948... em dízima.

    Se for considerar 234949 como arredondamento e levando em conta que isso ocorreria também em outro vetor, então:

    2 x 234949 = 469898, ou seja, 4,69898 x 10^5. O que ainda seria possível de ser executado dentro de 1 segundo. Em 1 segundo, geralmente valores de até 10^6 satisfazem. A partir de 10^7, o tempo começa a variar em milissegundos.