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