TOPIC

Time Limit Exceeded

tammyvitorino asked 6 years ago

Estou recebendo TLE nesse código, porém não encontrei uma forma de otimizar... Dentro dele tem uma função que inverte e calcula os swaps, mas não parece estar sendo tão eficaz quanto deveria. Alguém pode me dar uma luz:

    for i in range(tamanho):
        for j in range(i+1,tamanho):
            if vagoes[i] > vagoes[j]:
                swap = swap + 1
                x = vagoes[j]
                vagoes[j] = vagoes[i]
                vagoes[i] = x

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

  • tmjunior replied 4 years ago

    Poxa HENRIQUE MONTEIRO, não precisava desenterrar essa pra passar vergonha ao chamar o amiguinho de mentiroso kkkk

    Só porque você não conhece o famoso problema Counting Inversions não quer dizer que não exista uma solução ótima em N.log(N). O motivo pelo qual o algoritmo bubble sort consegue resolver essa questão é devido a uma propriedade muito importante dos algoritmos de ordenação chamada estabilidade. Portanto, qualquer algoritmo de ordenação estável consegue resolver este problema, inclusive o quick sort em sua versão estável. Recomendo a resolução do problema: https://www.urionlinejudge.com.br/judge/pt/problems/view/1892 que recebe TLE ao utilizar qualquer algoritmo quadrático.

    Fonte: https://www.geeksforgeeks.org/counting-inversions/

    MOD

  • Wanderson-IFCE-Tiangua replied 3 years ago

    Tarcisio Mazur Junior, obrigado! Me ajudou bastante.

  • hmonteiro1 replied 4 years ago

    RAPHAEL, não tem como contar o número de swaps usando merge sort.

  • Raphael5 replied 6 years ago

    Uma forma de otimizar pode ser contando com o merge sorte! ;D Tem muitas explicações na internet, a contagem de swaps com esse outro metodo de ordenação que é N x log(N) pra cada vetor

  • rcabr1 replied 6 years ago

    Sim, para você contar o número de swaps, é preciso ordenar o vetor, e isso exige uma complexidade de N*L^2. Acredito que você consiga sair do TLE se você conseguir contar os swaps com uma ordenação do vetor com um algoritmo da ordem de N*L*log(L)