来自量子世界的新技术---算法篇

来自量子世界的新技术—算法篇

1. 综述
   在量子世界里有两个算法非常重要，分别是shor，grover。Shor算法是用来解决大数质因子分解，如果其成功在硬件上实现，那么将会威胁到RSA加密算法；grover算法是实现无序数据库中搜索。
2. P,NP,NPC难题
   p问题，英文全称polynomial problem多项式问题可以在多项式时间内解决的问题，
   np 问题，英文全称non-deterministic polynomial，非确定性多项式问题，可以在多项式的时间里验证一个解的问题。
   看概率是一头雾水，换个熟悉的角度，从算法的时间复杂度来看；
   时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的增长的时间有多块。常见的复杂度包括，O(1)，O(n)，O(n!),0(n^2) ,O(a^n),O(lg(n))。其中按等级划分的话可以分为三类：
   第一类非多项式（超级复杂）：O(a^n)，O(n!)
   第二类多项式（可以接受）：O(1)，O(n)，0(n^2)
   第三类是最理想的O(lg(n))
   大多数我们所说的优化，算法改进，所要做的工作就是要将时间复杂度从第一类一直降到第三类，这样计算机的处理效率就高。
   第一类非多项式（超级复杂）：O(a^n)，O(n!)，我们为了解决这类复杂度的问题叫做NP问题，当然这个很片面，但可以这样直观的