忽然想到来着
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 2096 days ago, the information mentioned may be changed or developed.
 |
1
typetraits Sep 7, 2020  8
时间复杂度和硬件无关……
|
 |
2
xomix Sep 7, 2020
没有更换计算框架就变更计算逻辑的说法。
|
 |
3
bruce0 Sep 7, 2020 1
时间复杂度和算力没有关系,只和算法有关
只要算法没变,时间复杂度就不会变 算力提高,会降低计算时间 假设, 普通计算机需要算 10 分钟,量子计算机可能不用 1 秒就算完了 |
 |
4
misdake Sep 7, 2020
在最理想的情况下，在创建所有可能性之后，想要剔除掉不正确的答案也要 O(n)次检查吧
|
 |
5
flowfire OP @typetraits #1 物理规则改变之后。。。。是有关的
|
 |
6
kop1989 Sep 7, 2020 1
lz 的意思是，因为量子计算机是叠加态（即可以一次性得出所有组合），所以 n 无论是多少都是一次穷举 /回溯，所以都是 1 ？
不太了解量子计算机的本质原理，但是我理解是不是穷举可以一次性得出，但是回溯法是不是不行？ |
|
7
kop1989 Sep 7, 2020
而且穷举之后的检查能不能利用量子计算？毕竟检查输出的是布尔。
|
 |
8
across Sep 7, 2020
好像是的··· 穷举算力的会退化到 O(1)吧。 类似 GPU 并行处理机制，太早看的，忘了··· 反正 20 年里用不上。
|
 |
9
gwy15 Sep 7, 2020 10
n 皇后问题是 NP 完全问题，经典计算机最佳时间复杂度是 O(n!)，Rounak Jha, 2018 [1] 提出一种基于量子计算的算法，其时间复杂度为 O(N^3)，空间复杂度 O(N^2) 并在 IBM 量子实验平台上进行了模拟。
[1] A Novel Quantum N-Queens Solver Algorithm and its Simulation and Application to Satellite Communication Using IBM Quantum Experience. arXiv:1806.10221 |
 |
10
learningman Sep 7, 2020
楼上几位可能真错了，量子计算机不能算经典计算机
我记得新闻见过一个亿级库的 O(1)查找量子算法 |
 |
11
xupefei Sep 7, 2020 via iPhone
量子计算机不是非确定性图灵机。
|
 |
12
chocovon Sep 7, 2020
算法的复杂度确实跟硬件无关，降低复杂度的前提就是要换算法，只是量子计算机可以运行某些特定的算法而已
|
 |
13
elfive Sep 7, 2020 via iPhone
@typetraits #1 话没有错，不过应用到量子计算机上，肯定不是采用现在的算法了嘛，利用了量子的特性开发出来的算法，理论上是应该可以降低复杂度的。
|
 |
14
aguesuka Sep 8, 2020 via Android
说时间复杂度和算法无关的没学过模电吗？如果知道模拟电路里加减乘除模方对数都是 o(1)不知作何感想。
|
|
15
aguesuka Sep 8, 2020 via Android 1
"算法"=>"硬件"
|
 |
16
jorneyr Sep 8, 2020
查表法就是 O(1) 了 =_=!!!
|
 |
17
lengyihan Sep 9, 2020 via Android
量子计算机到底是啥。
|
Select Language