这个算法的时间复杂度是多少？

Question

编写一个带整数的程序,并打印出所有方法来乘以等于原始数字的较小整数,而不重复多组因子.换句话说,如果您的输出包含4*3,则不应再次打印3*4,因为这将是重复集.请注意,这不是仅要求素数分解.此外,您可以假设输入整数的大小合理; 正确性比效率更重要.PrintFactors(12)12*1 6*2 4*3 3*2*2

public void printFactors(int number) {
    printFactors("", number, number);
}

public void printFactors(String expression, int dividend, int previous) {
    if(expression == "")
        System.out.println(previous + " * 1");

    for (int factor = dividend - 1; factor >= 2; --factor) {
        if (dividend % factor == 0 && factor <= previous) {
            int next = dividend / factor;
            if (next <= factor)
                if (next <= previous)
                    System.out.println(expression + factor + " * " + next);

            printFactors(expression + factor + " * ", next, factor);
        }
    }
}

我觉得是这样的

如果给定数量是N并且素数因子的数量N = d,则时间复杂度是O(N ^ d).这是因为递归深度将达到素因子的数量.但它并不紧张.有什么建议？

Answer 1

2个想法：

该算法对输出敏感。输出分解最多消耗 O(N) 次循环迭代，因此总体来说我们有 O(N * number_of_factorizations)

另外，根据马斯特定理，方程为：F(N) = d * F(N/2) + O(N)，所以总的来说我们有O(N^log_2(d))