Ответ 1
Хорошо, это легкая победа в SortedList. Для вставки элемента требуется двоичный поиск (O (log (n)), чтобы найти точку вставки, затем List.Insert(O (n)), чтобы вставить элемент. Вставка() доминирует, заполнение списка требует O (n ^ 2).Если элементы ввода уже отсортированы, вставка сжимается до O (1), но не влияет на поиск. Теперь заполнение O (nlog (n)). Вы не волнуетесь, насколько велика О, Сначала сортировка всегда более эффективна. Предполагая, что вы можете позволить себе удвоенное требование к хранилищу.
SortedDictionary отличается, он использует красно-черное дерево. Поиск точки вставки требует O (log (n)). После этого может потребоваться повторная балансировка дерева, что также принимает O (log (n)). Таким образом, заполнение словаря принимает O (nlog (n)). Использование отсортированного ввода не изменяет усилия, чтобы найти точку вставки или перебалансировку, но все равно O (nlog (n)). Однако вопрос о том, что вставка отсортированного ввода требует, чтобы дерево постоянно перебалансировалось. Он работает лучше, если вход случайный, вам не нужен отсортированный вход.
Так заполняется 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 является сохранение сортировки коллекции после вставок. Если вы только беспокоитесь о заполнении, но не мутируете, вы не должны использовать эти коллекции.