.NET List <T>.Sort использует интросорт, почему наихудший случай O (n ^ 2)? - PullRequest
Новая
       50

.NET List <T>.Sort использует интросорт, почему наихудший случай O (n ^ 2)?

0 голосов
/ 17 ноября 2018

. В документации .NET List<T>.Sort упоминается асимптотическое время выполнения: https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.sort?view=netframework-4.7.2

В среднем этот метод является операцией O (n log n), где n - число;в худшем случае это операция O (n ^ 2).

Также упоминается, что она реализована с использованием Array.Sort, которая также имеет утверждение времени выполнения по адресу: https://docs.microsoft.com/en-us/dotnet/api/system.array.sort?view=netframework-4.7.2

Для массивов, отсортированных с использованием алгоритмов Heapsort и Quicksort, в худшем случае этот метод представляет собой операцию O (n log n), где n - длина.

Itтакже упоминается, что интросорт начал использоваться с .NET 4.5 в 2012 году.

Почему List<T>.Sort по-прежнему O (n ^ 2) в худшем случае?Или это просто ошибка в документации, и на самом деле это O (n log n)?

Ответы [ 2 ]

0 голосов
/ 17 ноября 2018

Introsort - это O (n log n) в худшем случае.

Насколько я знаю, единственная причина, по которой интросорт существует, в первую очередь, состоит в том, чтобы избежать O (n 2 ) времени наихудшего случая быстрой сортировки.

Таким образом, ссылка о том, что это O (n 2 ), неверна.

Обратите внимание, что две ссылки дают один и тот же алгоритм, дословно (минус то, что кажется ошибкой ввода - Log N вместо log N).

  • Если размер раздела меньше 16 элементов, он использует алгоритм сортировки вставкой

  • Если число разделов превышает 2 log n, где n - диапазон входного массива, он использует алгоритм Heapsort.

  • В противном случае используется алгоритм быстрой сортировки.

И все же они заканчиваются выводом о различных сложностях наихудшего случая.

в худшем случае этот метод является операцией O (n log n)

против

в худшем случае это операция O (n 2 )

0 голосов
/ 17 ноября 2018

Я думаю, что это может быть проблемой приближения. Возьми вторую цитату:

Для массивов, отсортированных с использованием алгоритмов Heapsort и Quicksort, в худшем случае этот метод является операцией O (n log n), где n - длина.

Я видел тонны учебников / статей, описывающих быструю сортировку как O (n log n), в то время как на самом деле вы можете дважды проверить здесь и убедиться, что его наихудшая стоимость в действительности равна O (n²). Это обычно происходит потому, что на практике быстрая сортировка почти всегда быстрее, чем другие алгоритмы сортировки, которые на бумаге имеют меньшую стоимость в худшем случае. Например, вы увидите, что для сортировки блоков в худшем случае O (n log n), но в большинстве практических приложений быстрая сортировка будет быстрее.

Что касается вашей первой цитаты: я бы сказал, что это потому, что в документах упоминается наихудший случай среди возможных случаев. В частности:

  • Если размер раздела меньше 16, он идет с сортировкой вставки, которая равна O (n²) (хотя это можно увидеть как O (1) здесь, поскольку она ограничена 16).
  • Если раздел […] идет с heapsort, то есть O (n log n).
  • В противном случае он идет с быстрой сортировкой, которая фактически равна O (n²).

Так что я бы сказал, что именно поэтому List<T>.Sort метод описывается как O (n log n) в среднем и O (n²) в худшем случае здесь.

...