该算法的时间复杂度是多少 [英] What is the time complexity of this algorithm

问题描述

编写一个使用整数的程序，并打印出所有方法以乘以等于原始数字的较小整数，而无需重复因子集。换句话说，如果您的输出包含4 * 3，则不应再次打印3 * 4，因为这将是重复集。请注意，这并非仅要求素因数分解。同样，您可以假定输入整数的大小是合理的。正确比效率更重要。 PrintFactors（12）12 * 1 6 * 2 4 * 3 3 * 2 * 2

Write a program that takes an integer and prints out all ways to multiply smaller integers that equal the original number, without repeating sets of factors. In other words, if your output contains 4 * 3, you should not print out 3 * 4 again as that would be a repeating set. Note that this is not asking for prime factorization only. Also, you can assume that the input integers are reasonable in size; correctness is more important than efficiency. 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）。这是因为递归深度将达到素数的数量。但这不是束缚。有建议吗？

If the given number is N and the number of prime factors of N = d, then the time complexity is O(N^d). It is because the recursion depth will go up to the number of prime factors. But it is not tight bound. Any suggestions?

推荐答案

2个想法：

算法已输出-敏感。输出因式分解最多要用到循环的O（N）次迭代，因此总体上我们有O（N * number_of_factorizations）

The algorithm is output-sensitive. Outputting a factorization uses up at most O(N) iterations of the loop, so overall we have O(N * number_of_factorizations)

另外，通过Master定理，方程式为： F（N）= d * F（N / 2）+ O（N），所以总体上我们有 O（N ^ log_2（d ））

Also, via Master's theorem, the equation is: F(N) = d * F(N/2) + O(N) , so overall we have O(N^log_2(d))

这篇关于该算法的时间复杂度是多少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！