Andrei Asked: 2025-04-28 18:14:09 +0800 CST2025-04-28 18:14:09 +0800 CST 2025-04-28 18:14:09 +0800 CST LINQ Order()/OrderBy() 和 Take(k) 的时间复杂度是多少？ 772 以下 C# 代码的时间复杂度是多少？ array.Order().Take(k).ToArray(); LINQ 会将其视为 QuickSelect 吗？还是会以复杂度O(n log n)执行完整的数组排序？ c# 2 个回答 Voted Best Answer canton7 2025-04-28T18:29:57+08:002025-04-28T18:29:57+08:00 文档并未保证此行为。但是，当前实现对 使用了部分快速排序 (QuickSort) .OrderBy().Skip/Take，对 使用了快速选择 (QuickSelect) .OrderBy().First/Last/ElementAt。 这意味着的时间复杂度.OrderBy().Take(k)是O(n + k log k)平均和O(n²)最差的。 这项功能早在 2016 年的拉取请求中就已实现（当时是 .NET Core 1.0）。这是一项刻意的优化，之前就已添加，因此实际上被移除的可能性很小。 Talal Habib 2025-04-28T18:20:07+08:002025-04-28T18:20:07+08:00 .Order()对整个进行排序，时间复杂度array为O(n log n) 。 .Take(k)和.ToArray()是O(k)运算。 总的来说，该代码的时间复杂度为： O（n log n） 它将执行完整排序O(n log n)，而不是快速选择 O(n)。
文档并未保证此行为。但是，当前实现对 使用了部分快速排序 (QuickSort)
.OrderBy().Skip/Take，对 使用了快速选择 (QuickSelect).OrderBy().First/Last/ElementAt。这意味着的时间复杂度
.OrderBy().Take(k)是O(n + k log k)平均和O(n²)最差的。这项功能早在 2016 年的拉取请求中就已实现（当时是 .NET Core 1.0）。这是一项刻意的优化，之前就已添加，因此实际上被移除的可能性很小。
.Order()对整个进行排序，时间复杂度array为O(n log n) 。.Take(k)和.ToArray()是O(k)运算。总的来说，该代码的时间复杂度为： O（n log n）
它将执行完整排序O(n log n)，而不是快速选择 O(n)。