忽然想到来着
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 2249 days ago, the information mentioned may be changed or developed.
 |
1
时间复杂度和硬件无关……
|
8 |
xomixSep 7, 2020
2
没有更换计算框架就变更计算逻辑的说法。
|
 |
3
时间复杂度和算力没有关系,只和算法有关
只要算法没变,时间复杂度就不会变 算力提高,会降低计算时间 假设, 普通计算机需要算 10 分钟,量子计算机可能不用 1 秒就算完了 |
 |
misdakeSep 7, 2020
4
在最理想的情况下，在创建所有可能性之后，想要剔除掉不正确的答案也要 O(n)次检查吧
|
 |
5
@typetraits #1 物理规则改变之后。。。。是有关的
|
 |
6
lz 的意思是，因为量子计算机是叠加态（即可以一次性得出所有组合），所以 n 无论是多少都是一次穷举 /回溯，所以都是 1 ？
不太了解量子计算机的本质原理，但是我理解是不是穷举可以一次性得出，但是回溯法是不是不行？ |
|
kop1989Sep 7, 2020
7
而且穷举之后的检查能不能利用量子计算？毕竟检查输出的是布尔。
|
 |
acrossSep 7, 2020
8
好像是的··· 穷举算力的会退化到 O(1)吧。 类似 GPU 并行处理机制，太早看的，忘了··· 反正 20 年里用不上。
|
 |
9
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 |
 |
learningmanSep 7, 2020
10
楼上几位可能真错了，量子计算机不能算经典计算机
我记得新闻见过一个亿级库的 O(1)查找量子算法 |
 |
xupefeiSep 7, 2020 via iPhone
11
量子计算机不是非确定性图灵机。
|
 |
chocovonSep 7, 2020
12
算法的复杂度确实跟硬件无关，降低复杂度的前提就是要换算法，只是量子计算机可以运行某些特定的算法而已
|
 |
elfiveSep 7, 2020 via iPhone
13
@typetraits #1 话没有错，不过应用到量子计算机上，肯定不是采用现在的算法了嘛，利用了量子的特性开发出来的算法，理论上是应该可以降低复杂度的。
|
 |
aguesukaSep 8, 2020 via Android
14
说时间复杂度和算法无关的没学过模电吗？如果知道模拟电路里加减乘除模方对数都是 o(1)不知作何感想。
|
|
15
"算法"=>"硬件"
|
 |
jorneyrSep 8, 2020
16
查表法就是 O(1) 了 =_=!!!
|
 |
lengyihanSep 9, 2020 via Android
17
量子计算机到底是啥。
|
Select Language