algorithm - 需要帮助分析该算法的时间复杂度

Question

有一种算法要求我们打印出一个数的质因数的所有子序列。 例如，如果数字是 6，我们将打印:

{}、{2}、{3}、{2 3}

现在给定的约束条件是一个数的质因数不能超过 13。

复杂度显然是O(pow(2, prime factors of the number))

现在，我的疑问是: 由于我们知道小于或等于 13 的素数只有 6 个。这使得最坏的时间复杂度 O(pow(2, 6)) 显然是 O(1)。那么，我们是否可以将该算法称为常数时间算法，因为我们已经知道所有可能的时间复杂度候选常数值？

Answer 1

没那么快。

如果k = 2<sup>n<sub>2</sub></sup> * 3<sup>n<sub>3</sub></sup> * 5<sup>n<sub>5</sub></sup> * 7<sup>n<sub>7</sub></sup> * 11<sup>n<sub>11</sub></sup> * 13<sup>n<sub>13</sub></sup>那么子序列的数量是(n<sub>2</sub>+1) * (n<sub>3</sub>+1) * (n<sub>5</sub>+1) * (n<sub>7</sub>+1) * (n<sub>11</sub>+1) * (n<sub>13</sub>+1)这些序列的平均长度是(n<sub>2</sub> + n<sub>3</sub> + n<sub>5</sub> + n<sub>7</sub> + n<sub>11</sub> + n<sub>13</sub>)/2很容易确定这些术语中的每一个都是O(log(k))。 .由此，您可以设置上限 O(log(k)<sup>7</sup>)关于输出的大小。 (如果每个 p<sup>n<sub>p</sub></sup> ≈ k<sup>1/6</sup> 都为 p，那么所有 6 个项都同时具有该比例。)

如果数字没有开始分解，则必须先添加分解数字的难度。