-6
Я ищу алгоритм, который принимает O(1) время как для search and insertion.Есть ли какой-нибудь алгоритм, который принимает O (1) раз?
Есть ли доступный алгоритм? Является ли это возможным?
A
ответ
1
Теоретически у вас есть вставка O (1) и поиск хэш-карты, предполагая, что хеш является совершенным, а время вычисления хэша - O (1).
+0
Если хэш-карта не будет переполнена данными, которые будут помещены в его структуру данных. – Vesper
-3
Невозможно. Чтение ключей, на которые вы вставляете, будет лучше O (log n), поскольку ключ должен быть представлен в двоичном формате. Таким образом, каждый раз, когда вы удваиваете размер, вам нужно добавить дополнительную двоичную цифру в ключ, и поэтому он не будет O (1). Не говоря уже о фактическом введении значения.
Если мы не говорим о квантовых вычислениях?
+0
Компьютеры читают слова 16 или 32 бита за раз. Ваша логика ускользает от меня. – EJP
+0
Или 64 бит. Что это связано с O (...)? –
+0
O (1) подразумевает постоянное количество времени для вставки в любую коллекцию размеров. Двойной размер коллекции, и он не влияет на время. Но каждый раз, когда я удваиваю размер коллекции, мне нужен более длинный ключ для представления элемента в коллекции. Для считывания ключа используется клавиша O (n), а ключ пропорционален log (m) количеству элементов в коллекции. –
Смежные вопросы
- 1. Является ли этот алгоритм O (1)?
- 2. Докажите, что алгоритм, который принимает (n + 1)^5 шагов, равен O (n^5)?
- 3. Алгоритм записи O O
- 4. Реализация алгоритма Max, который является O (1)
- 5. Есть ли итератор, который принимает сложный страж?
- 6. Может ли операция, которая принимает O (1) амортизированное время, имеет наихудшее время O (n^2)?
- 7. Имеется ли алгоритм сортировки, который имеет временную сложность O (N)?
- 8. Алгоритм кластеризации, который принимает произвольную функцию расстояния
- 9. Есть ли алгоритм O (n) для построения макс-кучи?
- 10. Алгоритм O (N) медленнее, чем алгоритм O (N logN)
- 11. Преобразовать алгоритм из O (N) к о (1)
- 12. Алгоритм сортировки O (n)
- 13. Выбор O (n) над O (1), когда для всех n, O (1) быстрее, чем O (n)?
- 14. Есть ли способ получить элемент из набора в O (1) раз?
- 15. O (n) алгоритм, который возвращает индексы массива, если условие истинно
- 16. Который больше: O (n * logn) или O (1)?
- 17. Путаница с O (1)
- 18. В Ruby, Python или PHP есть ли вставка в середину объекта Array, который занимает O (1) раз?
- 19. Действительно ли печать строки действительно принимает O (n)?
- 20. Алгоритм для O (1) взвешенного случайного выбора с удалением
- 21. Есть ли разрешенная матрица в Matlab, позволяющая считывать ввод данных в O (1) раз?
- 22. O (N) Алгоритм сортировки
- 23. Интервальный алгоритм поиска с O (1) скоростью поиска
- 24. Есть ли какая-либо функция, которая находится в o (1)?
- 25. Большой O-O (N^2) или O (N^2 + 1)?
- 26. большой алгоритм O-сортировка
- 27. алгоритм экспоненциального умножения, который работает в O (n) времени?
- 28. Существует ли целочисленный алгоритм сортировки O (n)?
- 29. Алгоритм вычисления TripleSum O (n) time, Java
- 30. Можно ли отсортировать массив в O (n), если есть только элементы от 1 до n?
Ум, хеш-стол? .. – dasblinkenlight
Алгоритм делать ** что **? – angelatlarge
Но время вставки в хеш-таблице равно O (n) в худшем случае. – mumair