time-complexity - 具有包含无理指数的运行复杂性的算法

Question

嗨，我想知道是否有任何算法具有包含无理指数的运行复杂性。Strassen 的矩阵乘法算法是我正在寻找的东西，但还有更多吗？

标签： time-complexitylogarithmexponential

Answer 1

一个带有一些示例的小列表：

• 计算数论中的一些算法的复杂性用L 表示法表示，其中一些具有无理指数特征：Lenstra 的椭圆曲线分解、Dixon 分解、索引演算算法。
• Stooge Sort的复杂性在于指数log(3)/log(3/2)是一个无理数。
• 汤姆库克乘法。
• 据称，所有 SAT 求解器的复杂性都具有非理性指数
• 以下列表

但更一般地说，应该可以挖掘（甚至监控）维基百科的算法列表，解析和提取与时间复杂度相关的数学表达式，并可能将表达式列表输入CAS（例如SymPy使用转换器，如latex2sympy）能够确定是否涉及任何非理性指数（如果维基数据具有完整的结构化数据覆盖范围，它可能是更好的选择，例如：wikidata 的快速排序页面）。也可以将这个数据收集扩展到维基百科之外，进入显然提供乳胶来源的 arXiv对于某些文章，然后使用乳胶解析器和表达式解析器来查找这些类型的复杂性。