量子计算机处理“基于比较的排序”复杂度可以降到
基于比较的排序时间复杂度只能到nlogn，不管用的是不是量子计算机，这是信息论原理得出的结论。因为排序相当于给定n元素序列，在其全排列(n!种)中选择一个，而一次比较只能给出1bit信息，想要使总信息多到n!至少需要log2(n!) = log2(1) + log2(2) + ... + log2(n) \u0026lt; n * log2(n)次比较。量子计算机最著名的应该是Shor算法，可以在多项式时间内将合数分解成质数以及求有限群上的离散对数，而最快的传统计算机算法也是指数级的，这也是现代公钥密码系统的理论基础。另外一个例子是Grover算法，可以在n^(1/2)步内搜索无序序列，在传统计算机上至少要n步。
■网友
如果是基于比较的排序，O(n log n)已经是最低了，从这一角度来看，量子计算机没有办法比快排还快。如果可用的内存有限而数据量很大，量子计算机有可能能够加速。有一种说法是Quantum Bogosort能够在O(n)内完成排序，但这应该只是一种圈内笑话。要对n个元素进行随机化需要log(n!)个量子比特，但是一台计算机的比特数总是有限的；另外Bogosort算法要求发现排序不对的时候毁灭宇宙，我觉得这个应该没有办法做到。
推荐阅读
- 济南垃圾处理单位“前分后混”将面临最高十万元罚款
- 汽车知识|捷达库存成灾，特价处理，4S店卖不动，大家都不差钱！
- 想要入门图像处理，应该从哪本书看起
- 学图像处理有哪些不错的书推荐
- 关于用phpfsocket 写Post， 模拟http 报文怎样写入要传输的处理数据
- 大部分黑客或安全研究员读的是啥「大学专业 」
- 在哈尔滨工业大学计算机系就读是啥样的体验
- 计算机技术与科学专业怎样利用高中毕业的暑假
- 非计算机专业想要利用课余时间深入自学C++，想要找到比较体面的工作大概需要啥水平
- 孩子|小孩发烧的处理方法有物理降温与药物退烧！但很多新手父母不会