Início / coding / Perguntas / 79596224
Accepted
Andrei
Asked: 2025-04-28 18:14:09 +0800 CST

Qual é a complexidade de tempo de LINQ Order()/OrderBy() seguido por Take(k)?

  • 772

Qual é a complexidade de tempo do seguinte código em C#?

array.Order().Take(k).ToArray();

O LINQ tratará isso como QuickSelect? Ou realizará uma ordenação completa de arrays com complexidade O(n log n) ?

c#

2 respostas

  1. Best Answer

    Este comportamento não é garantido pela documentação. No entanto, a implementação atual usa um QuickSort parcial para .OrderBy().Skip/Take, e um QuickSelect para .OrderBy().First/Last/ElementAt.

    Isso significa que a complexidade de tempo .OrderBy().Take(k)é O(n + k log k)Média e O(n²)Pior.

    Isso foi implementado neste pull request em 2016 (ou seja, no .NET Core 1.0). Foi uma otimização deliberada, adicionada há algum tempo, o que significa que há pouquíssimas chances de ser removida na prática.

    • 7

    1. .Order()classifica todo o array, que é O(n log n) de complexidade de tempo.

    2. .Take(k)e .ToArray()são operações O(k) .

      No total, a complexidade de tempo deste código é: O(n log n)

      Ele executará a classificação completa O(n log n), não a Seleção rápida O(n).

    • -2

relate perguntas