这是一个创建于 1563 天前的主题，其中的信息可能已经有所发展或是发生改变。
忽然想到来着
 |
1
typetraits 2020-09-07 16:45:09 +08:00  8
时间复杂度和硬件无关……
|
 |
2
xomix 2020-09-07 16:48:24 +08:00
没有更换计算框架就变更计算逻辑的说法。
|
 |
3
bruce0 2020-09-07 16:48:52 +08:00 1
时间复杂度和算力没有关系,只和算法有关
只要算法没变,时间复杂度就不会变 算力提高,会降低计算时间 假设, 普通计算机需要算 10 分钟,量子计算机可能不用 1 秒就算完了 |
 |
4
misdake 2020-09-07 16:58:37 +08:00
在最理想的情况下，在创建所有可能性之后，想要剔除掉不正确的答案也要 O(n)次检查吧
|
 |
5
flowfire OP @typetraits #1 物理规则改变之后。。。。是有关的
|
 |
6
kop1989 2020-09-07 17:23:03 +08:00 1
lz 的意思是，因为量子计算机是叠加态（即可以一次性得出所有组合），所以 n 无论是多少都是一次穷举 /回溯，所以都是 1 ？
不太了解量子计算机的本质原理，但是我理解是不是穷举可以一次性得出，但是回溯法是不是不行？ |
|
7
kop1989 2020-09-07 17:24:06 +08:00
而且穷举之后的检查能不能利用量子计算？毕竟检查输出的是布尔。
|
 |
8
across 2020-09-07 17:24:29 +08:00
好像是的··· 穷举算力的会退化到 O(1)吧。 类似 GPU 并行处理机制，太早看的，忘了··· 反正 20 年里用不上。
|
 |
9
gwy15 2020-09-07 17:29:44 +08:00 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 2020-09-07 19:05:48 +08:00
楼上几位可能真错了，量子计算机不能算经典计算机
我记得新闻见过一个亿级库的 O(1)查找量子算法 |
 |
11
xupefei 2020-09-07 19:15:27 +08:00 via iPhone
量子计算机不是非确定性图灵机。
|
 |
12
chocovon 2020-09-07 20:48:27 +08:00
算法的复杂度确实跟硬件无关，降低复杂度的前提就是要换算法，只是量子计算机可以运行某些特定的算法而已
|
 |
13
elfive 2020-09-07 21:15:42 +08:00 via iPhone
@typetraits #1 话没有错，不过应用到量子计算机上，肯定不是采用现在的算法了嘛，利用了量子的特性开发出来的算法，理论上是应该可以降低复杂度的。
|
 |
14
aguesuka 2020-09-08 00:10:20 +08:00 via Android
说时间复杂度和算法无关的没学过模电吗？如果知道模拟电路里加减乘除模方对数都是 o(1)不知作何感想。
|
|
15
aguesuka 2020-09-08 00:12:07 +08:00 via Android 1
"算法"=>"硬件"
|
 |
16
jorneyr 2020-09-08 09:00:18 +08:00
查表法就是 O(1) 了 =_=!!!
|
 |
17
lengyihan 2020-09-09 20:58:48 +08:00 via Android
量子计算机到底是啥。
|
Select Language