Início / coding / Perguntas / 79550092
Accepted
Samson
Asked: 2025-04-02 16:28:26 +0800 CST

Limite de tempo excedido no Leetcode 128, mesmo para complexidade de tempo ideal

  • 772

Eu estava tentando resolver a questão 128 do LeetCode. Maior sequência consecutiva :

Dado um array não classificado de inteiros nums, retorne o comprimento da maior sequência de elementos consecutivos .

Você deve escrever um algoritmo que seja executado no O(n)tempo.

Exemplo 1:

Entrada: nums = [100,4,200,1,3,2]
Saída: 4
Explicação: A sequência de elementos consecutivos mais longa é [1, 2, 3, 4]. Portanto, seu comprimento é 4.

Restrições:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Minha primeira tentativa fez classificação seguida de contagem. Isso tem complexidade de tempo O(nlogn), mas surpreendentemente me deu 93,93% de percentil para complexidade de tempo (40ms).

Então reli a questão e percebi que a resposta deve estar em complexidade de tempo O(n). Então escrevi o seguinte código:

def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        longest_streak = 0
        
        for num in nums:
            if (num - 1) not in s:
                current_streak = 1
                while (num + 1) in s:
                    num += 1
                    current_streak += 1
                longest_streak = max(longest_streak, current_streak)
            
        return longest_streak

(Eu sei, não é uma boa prática reutilizar o nome da variável num no loop aninhado, mas isso não vem ao caso. Eu testei usando uma variável separada também com o mesmo resultado abaixo)

Embora isso devesse teoricamente ter complexidade de tempo O(n), mais rápido que minha primeira solução, isso na verdade resultou em limite de tempo excedido para alguns casos e meu código foi rejeitado.

Acabei enviando uma solução de aprovação após consultar a solução

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        longest_streak = 0
        
        for num in nums:
            if (num - 1) not in nums:
                next_num = num + 1
                while next_num in nums:
                    next_num += 1
                longest_streak = max(longest_streak, next_num - num)
            
        return longest_streak

onde identifiquei 2 diferenças principais:

  1. Reatribuí nums a um conjunto no local em vez de uma nova variável
  2. Usei next_num em vez de manter uma variável current_streak

No entanto, ambas as mudanças não parecem ter impacto significativo no tempo de execução, o suficiente para cruzar a linha entre o limite de tempo excedido e uma solução de passagem. Para me confundir ainda mais, essa solução O(n) ainda teve um desempenho pior do que minha solução de classificação, classificando-se apenas no percentil 75,73% (46 ms).

Então minhas perguntas são:

  1. Por que um algoritmo O(nlogn) tem desempenho mais rápido que O(n) na prática?
  2. Por que meu primeiro algoritmo O(n) é tão lento que atingiu o limite de tempo excedido, enquanto meu segundo algoritmo com alterações mínimas conseguiu passar?
python

3 respostas

  1. Best Answer

    Por que um algoritmo O(nlogn) tem desempenho mais rápido que O(n) na prática?

    A complexidade de tempo não diz nada sobre os tempos de execução reais para tamanhos de entrada concretos. Ela diz apenas algo sobre como os tempos de execução evoluirão assintoticamente conforme o tamanho da entrada cresce.

    Em geral (não relacionado ao código real que você apresentou), podemos imaginar um algoritmo O(𝑛) que precisa de 1000 + 𝑛 milissegundos para ser concluído, e um algoritmo O(𝑛log𝑛) que precisa de 1 + 𝑛log 10 𝑛 milissegundos para ser concluído. E agora fica claro como o algoritmo O(𝑛log𝑛) vencerá o O(𝑛) para muitos tamanhos de entrada realistas.

    Veja quantos milissegundos eles precisariam para valores concretos de 𝑛:

    𝑛 O(𝑛) O(𝑛log𝑛)
    1 1 010 1
    10 1 100 11
    100 2 000 201
    1000 11 000 3 001
    10000 101 000 40 001
    100000 1 001 000 500 001
    1000000 10 001 000 6 000 001
    10000000 100 001 000 70 000 001
    100000000 1 000 001 000 800 000 001
    1000000000 10 000 001 000 9 000 000 001
    10000000000 100 000 001 000 100 000 000 001
    100000000000 1 000 000 001 000 1 100 000 000 001

    Por definição, há sempre um 𝑛 acima do qual a melhor complexidade de tempo vencerá, mas, como você pode ver, pode ser um limite muito alto para 𝑛: na tabela acima, apenas a última linha mostra uma vitória para o algoritmo teoricamente mais eficiente.

    Por que meu primeiro algoritmo O(n) é tão lento que atingiu o limite de tempo excedido, enquanto meu segundo algoritmo com alterações mínimas conseguiu passar?

    É por causa do loop externo. Na versão lenta, ele itera sobre a lista de entrada, enquanto na versão mais rápida, ele itera sobre o conjunto. Isso significa que se a entrada for grande e tiver muitos valores duplicados, a versão lenta está repetindo um trabalho que não traz nenhum benefício. Sua versão inicial só precisa substituir isso para terminar o trabalho dentro do limite de tempo fornecido:

    Mudar:

    for num in nums:

    para:

    for num in s:
    • 3

  2. Sua primeira tentativa O(n) não é O(n), mas O(n^2), mesmo assumindo que as pesquisas de conjunto são O(1). Considere uma entrada como esta:

    nums = [0] * 50000 + list(range(50000))

    Isso levaria vários minutos para o seu código.

    Seu

            for num in nums:
            if (num - 1) not in s:

    obtém num = 050001 vezes e a ifcondição é verdadeira todas as vezes, então você verifica toda a sequência até 49999 todas as vezes.

    Sua versão melhorada evita isso porque obtém num = 0apenas uma vez, pois o conjunto remove todas as suas duplicatas. É O(n) como pretendido (assumindo que as pesquisas de conjunto são O(1)).

    • 1

  3. Primeiro de tudo, nenhuma dessas variantes de código tem a complexidade de O(N), já que contém o ciclo aninhado. Este é o(n*m), e em n == m resulta O(n**2). Apenas o ciclo 'flat' tem a complexidade de O(n). Ou se m for sempre igual a 1/0, que simplesmente cancela a iteração.

    Agora vamos para seu primeiro código. Primeiro: o ciclo FOR passa pela lista e pelo conjunto. A lista aleatória pode parecer assim: [2, 3, 3, 3, ... 100,500 More Times ..., 1]. E seu ciclo passará todos os 100.500 elementos iguais e cada vez lançará uma verificação inútil. Segundo:

    while (num + 1) in s:
    num += 1

    SECO, Não Repita Você Mesmo))) Do zero você aumentou o número de operações em 100%. Todas essas 'pequenas coisas' deram o resultado que você vê.

    Se falamos de otimização, então esta não é a melhor opção de código (sim, eu encontrei a fonte de onde você tirou esta decisão :)). Não é necessário verificar os mesmos elementos muitas vezes seguidas quando já se sabe com certeza que eles não serão mais necessários. Set () é a mesma estrutura de dados rápida e ao executar operações de comparação/adição/subtração. Portanto, será lógico depois de encontrar cada sequência remover todos os seus elementos do conjunto, eles não são mais necessários. Inicie este código (ou crie uma lista de qualquer comprimento, por exemplo, [random.randrange (1000) para _ em Range 100_000] e compare o número de operações que concluíram o primeiro e o segundo fragmentos do código para obter o resultado.

    PS: Peço desculpas pela gramática, escrevo através do tradutor.

    lst = [44, 17, 57, 64, 90, 5, 44, 43, 99, 33, 31, 52, 55, 50, 2, 58, 12, 32, 27,
 73, 5, 12, 45, 86, 52, 40, 3, 68, 17, 87, 34, 71, 23, 17, 60, 47, 66, 47, 95,
 67, 82, 92, 75, 13, 35, 7, 48, 13, 35, 74, 10, 63, 26, 48, 14, 38, 85, 72, 73,
 0, 75, 61, 88, 49, 90, 65, 80, 35, 55, 96, 73, 88, 69, 59, 29, 5, 4, 36, 84,
 21, 36, 34, 44, 91, 97, 3, 50, 31, 54, 27, 79, 7, 22, 38, 85, 76, 80, 35, 2, 87]

set_1 = set(lst)
set_2 = set()
res = 0
steps = 0

def longest_consecurtive(arg: set[int]) -> int:
    global steps
    streak = 0
    x = 0
    for x in arg:
        steps += 1
        if x - 1 not in arg:
            set_2.add(x)
            streak += 1
            break
    while (x := x + 1) in arg:
        steps += 1
        set_2.add(x)
        streak += 1
    return streak


while s := set_1 - set_2:
    steps += 1
    res = max(longest_consecurtive(s), res)

print(res)
print(f'Solution by sets finished in {steps} steps\n')

steps = 0


class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        # Create a set from the list for O(1) lookups
        num_set = set(nums)
        longest_streak = 0

        # Iterate over each number in the list
        for number in nums:
            global steps
            steps += 1
            # Check if it's the start of a sequence
            if number - 1 not in num_set:

                # Initialize the current number as the possible start of a sequence
                current_num = number
                current_streak = 1

                # Increment the current_num to find the length of the streak
                while current_num + 1 in num_set:
                    steps += 1
                    current_num += 1
                    current_streak += 1

                # Update the longest_streak with the maximum streak found
                longest_streak = max(longest_streak, current_streak)

        # Return the length of the longest consecutive sequence
        return longest_streak


res = Solution()
print(res.longestConsecutive(lst))
print(f'Soluton by list finished in {steps} steps')
    • -1

relate perguntas