3、计算数论与量子计算数论：概念、问题与算法
计算数论与量子计算数论：概念、问题与算法
1. 算法复杂度基础
在算法分析中，算法的运行时间是衡量其效率的关键指标。如果一个问题可以由一个算法在期望运行时间 $T(n) = O(Ln(1, c))$ 内解决，那么这个算法就是指数时间算法，相应的问题就是难题。这里需要注意的是，由于 $\log n$ 是输入的长度，$O((\log n)^{12})$ 属于多项式时间复杂度，而 $O((n)^{0.1})$ 则不是，因为 $O((n)^{0.1}) = O(2^{0.1 \log n})$，这是指数复杂度。
若一个算法的复杂度满足 $T(n) = O(Ln(\alpha, c))$，其中 $0 < \alpha < 1$，则该算法具有亚指数时间复杂度。亚指数时间复杂度处于多项式时间复杂度和指数时间复杂度这两个极端之间，是一个重要且有趣的类别。许多数论算法，如整数分解和离散对数算法，都属于这一特殊类别，它们比多项式时间算法慢，但比指数时间算法快。
复杂度类型总结
| 复杂度类型 | 条件 | 示例 |
|---|---|---|
| 指数时间复杂度 | $T(n) = O(Ln(1, c))$ | $O((n)^{0.1})$ |
| 多项式时间复杂度 | 如 $O((\log n)^{k})$（$k$ 为常数） | $O((\log n)^{12} |