Квантове сортування
Перейти до навігації
Перейти до пошуку
Квантове сортування — це будь-який алгоритм сортування, який працює на квантовому комп'ютері. Будь-який алгоритм квантового сортування на основі порівняння займе принаймні кроків,[1] що вже можна досягти класичними алгоритмами. Отже, для цієї задачі квантові комп'ютери нічим не кращі за класичні, і їх слід знехтувати, коли йдеться про часову складність. Однак у сортуванні з обмеженим простором квантові алгоритми перевершують класичні аналоги.[2]
- ↑ Høyer, P.; Neerbek, J.; Shi, Y. (2001). Quantum complexities of ordered searching, sorting, and element distinctness. 28th International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science. Т. 2076. с. 62—73. arXiv:quant-ph/0102078. doi:10.1007/3-540-48224-5_29. ISBN 978-3-540-42287-7.
- ↑ Klauck, Hartmut (2003). Quantum Time-Space Tradeoffs for Sorting. Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. с. 69. arXiv:quant-ph/0211174. doi:10.1145/780542.780553. ISBN 1581136749.
| Теорія |  | |
|---|---|---|
| Сортування обміном | ||
| Сортування вибором | ||
| Сортування включенням | ||
| Сортування злиттям | ||
| Алгоритми без порівнянь | ||
| Інші | ||
| Непрактичні алгоритми | ||