1
Я думаю, что создается новый ImmutableList из N + 1 элементов. Таким образом, его сложность должна быть O (N).Почему ImmutableList имеет сложность O (logN) в методе добавления?
A
ответ
3
Причина ImmutableList имеет O (журнал N) сложность объясняется here:
Почему неизменные типы более склонны к O (журнал п), где изменяемые типы O (1)? Это следствие внутренних структур данных , которые позволяют совместно использовать экземпляры коллекций. Например, изменяемый HashSet выделяет один массив и сохраняет элементы в , что этот массив имеет индекс, определяемый их хэш-кодом. Это поставщики O (1) время поиска и хранения. Если ImmutableHashSet использовал этот такой же тип хранения данных, то для каждой мутации потребуется , перераспределяющая и копирующая весь массив только для изменения одной записи, , которая бы быстро увеличивала производительность и давление газа, поскольку коллекции стали большими. Вместо этого эти неизменные коллекции используют неизменяемые сбалансированные двоичные деревья для хранения своих данных, , что позволяет очень эффективно использовать обмен данными между мутантными экземплярами коллекций. Однако, как результат , для каждого поиска или изменения требуется обход дерева , который имеет (в худшем случае) алгоритмическую сложность O (log n).
MSDN documentation for ImmutableArray дает некоторое представление и показывает разницу между сложностями ImmutableArray и ImmutableList:
+1
Эта документация находится на 'ImmutableList
+0
Удалена неверная ссылка. Я попытаюсь найти другую документацию MSDN. –
Смежные вопросы
- 1. Медиана BST в O (logn) временная сложность
- 2. Is O (LogN) == O (3LogN)?
- 3. Какова временная сложность этого фрагмента кода? O (n) или O (logn * logn)
- 4. Сложность O (n^3) vs O ((logn)^4))
- 5. на месте быстрая сортировка имеет сложность пространства O (n) или O (logn)
- 6. Почему TreeSet Iteration O (n) вместо O (n * logn)?
- 7. Большая сложность O в алгоритмах
- 8. сложность в терминах больших O
- 9. Почему IN() считается операцией O (logN)?
- 10. Общая сложность времени в методе
- 11. Любая коллекция .net, которая имеет сложность 0 (1) или O (Logn) для поиска и удаления, добавления и вставки
- 12. Высота дерева AVL в O (logn)
- 13. O (n^2) больше O ((n^2) logn)
- 14. Сравнение O ((logn)^const) с O (n)
- 15. Сравнение O ((logn)!) И O (2^n)
- 16. Имеется ли алгоритм сортировки, который имеет временную сложность O (N)?
- 17. Почему std :: list :: reverse имеет сложность O (n)?
- 18. Почему не сортировка бисера имеет теоретическую временную сложность O (n)?
- 19. Почему следующий код имеет только пространственную сложность O (N)?
- 20. Php: какая сложность [i.e O (N), O (1), ...], функция добавления квадратных скобок имеет? т.е. $ х [] = «значение»
- 21. Является бинарным поиском упорядоченного списка O (logN) в Elixir?
- 22. BIg O Обозначение: n * logn
- 23. Бит подсчитывается с 0 ~ N в O (logn)
- 24. Является ли O (logn) всегда деревом?
- 25. Почему deckey в алгоритме Дейкстры принимает время O (logN)?
- 26. Найти алгоритм в RBTREE в O (LOGN)
- 27. Почему пространственная сложность этого алгоритма O (n)?
- 28. Докажите, что logn равно O (2^sqrt (logn))
- 29. Почему эта сложность времени O (n)?
- 30. Какова сложность добавления матрицы?
Ну, они решили сделать его более эффективным, чем наивная реализацию. Что в этом плохого? –
Ваша вера в то, что создан новый список с большим количеством элементов, неверен. Помните, что неизменяемость означает, что вы можете * безопасно повторно использовать * части существующей структуры для построения новой структуры. Это повторное использование обеспечивает высокую эффективность во многих сценариях. –
Если вы хотите узнать больше об эффективных чисто функциональных структурах данных, я бы рекомендовал взглянуть на книгу Криса Окасаки. – TheInnerLight