Что такое временная и пространственная сложность словаря?
Давайте предположим, что у меня есть данные размером N (т.е.N элементов), и словарь был создан с емкостью N. Какова сложность:
- пробел - всего словаря
- время - добавление записи в словарь
MS обнаружил только, что поиск записи близок к O(1). Но как насчет отдыха?
3 ответа
Временная сложность добавления новой записи описана в разделе Dictionary<T>.Add():
Если значение Count меньше емкости, этот метод подходит к операции O(1). Если емкость должна быть увеличена для размещения нового элемента, этот метод становится операцией O(n), где n - число.
В чем сложность пространства - всего словаря
Словарь использует структуру данных ассоциативного массива, которая имеет O(N) пространственную сложность.
Msdn говорит: "Класс Dictionary реализован в виде хеш-таблицы". И хэш-таблица по очереди использует ассоциативные массивы.
В чем сложность времени - добавление записи в словарь
Однократное добавление занимает амортизированное O(1) время. В большинстве случаев это O(1), оно меняется на O(N), когда базовая структура данных должна увеличиваться или уменьшаться. Поскольку последнее случается нечасто, люди используют слово "амортизированный".
Официально не задокументировано, но широко заявлено (и видно из разборки), что базовое хранилище представляет собой массив пар имя-значение. Таким образом, сложность пространства равна O (n).
Поскольку это не является частью спецификации, теоретически это может измениться; но на практике это маловероятно, потому что это может изменить производительность различных операций (например, перечисление), которые могут быть видны.