Ну, это простой выигрыш в SortedList. Для вставки элемента требуется двоичный поиск (O (log (n)), чтобы найти точку вставки, затем List.Insert (O (n)) для вставки элемента. Доминирует Insert (), для заполнения списка требуется O (n). ^ 2). Если входные элементы уже отсортированы, то вставка сворачивается в O (1), но не влияет на поиск. Заполнение теперь O (nlog (n)). Вы не волнуетесь, насколько велик Oh, сортировка во-первых всегда более эффективна. Предполагая, что вы можете позволить себе удвоить требования к хранилищу.
SortedDictionary отличается, он использует красно-черное дерево. Нахождение точки вставки требует O (log (n)). Впоследствии может потребоваться перебалансировка дерева, что также требует O (log (n)). Заполнение словаря, таким образом, занимает O (nlog (n)). Использование отсортированного ввода не меняет усилия по поиску точки вставки или перебалансировке, оно все равно равно O (nlog (n)). Теперь значение Oh имеет значение, однако для вставки отсортированного ввода требуется постоянное перебалансирование дерева. Это работает лучше, если ввод случайный, вам не нужно сортировать ввод.
Таким образом, заполнение SortedList отсортированным вводом и заполнение SortedDictionary несортированным вводом равно O (nlog (n)). Игнорируя стоимость предоставления отсортированного ввода, Oh of SortedList меньше Oh of SortedDictionary. Это деталь реализации из-за того, как List выделяет память. Это нужно сделать только O (log (n)) раз, красно-черное дерево должно выделить O (n) раз. Очень маленький О, кстати.
Примечательно, что ни один из них не сравнивается выгодно с простым заполнением списка и последующим вызовом Sort (). Это также O (nlog (n)). На самом деле, если входные данные уже случайно отсортированы, вы можете обойти вызов Sort (), это сводится к O (n). Анализ затрат теперь должен перейти к усилиям, необходимым для сортировки входных данных. Трудно обойти фундаментальную сложность Sort (), O (nlog (n)). Он может быть невидим, можно отсортировать входные данные, скажем, по запросу SQL. Это займет больше времени, чтобы завершить.
Смысл использования SortedList или SortedDictonary - сохранять коллекцию отсортированной после вставок. Если вы беспокоитесь только о заполнении, но не о мутировании, вам не следует использовать эти коллекции.