时间戳

首页 > 解决方案 > for循环内递归分解函数的时间复杂度

time-complexity - for循环内递归分解函数的时间复杂度

问题描述

这是我的伪代码算法：它的作用是返回一个素数列表，该列表给出数字 n 的因式分解。例如，75 = 3 * 5 * 5

public static ArrayList<Integer> FACTORISATION(int n) {
    if (PRIME(n)) {
        // return a one-element array
        return new ArrayList<Integer>(Arrays.asList(n));
    } else {
        // find a prime divisor, p
        for (int i = 2; i < Math.sqrt(n); i++) {
            if (n % i == 0) {
                ArrayList<Integer> newList = new ArrayList<>();
                newList.add(i);
                newList.addAll(FACTORISATION(n/i));
                return newList;
            }
        }
    }
    return new ArrayList<>();
}

根据我的说法，时间复杂度可以计算为：-

T(n) = 2 + T(n-1/p) + T(n-2/p) +...
T(n) = nT(n-1/p)
T(n) = O(n!)

该PRIME(n)方法的复杂度为O(n)

这个对吗？

标签： time-complexitybig-o

解决方案

这有点复杂。首先，请更正代码中的错误，它应该i <= Math.sqrt(n);代替i < Math.sqrt(n);.

让我们从整数的唯一表示开始，作为其主要除数的幂的乘积：

n = p 1 a 1 p 2 a 2 p 3 a 3 ...p k a k

（例如，120 = 2 3 3 1 5 1）。代码中的循环将执行多少次for输入n（不计算递归子调用）？确切的i-1时间，哪里i是 的最小素数除数n。这是因为当i找到第一个这样的，循环终止（return newList;语句）。如果n本身是素数，for则根本不会执行循环，因为if (PRIME(n))将返回true。

对于哪些输入参数将FACTORISATION(int n)被调用（递归）？注意，会调用n，然后for

n/p 1 ,

n/p 1 2 ,

..

n/p 1一1 ,

n/p 1一1 p 2 ,

n/p 1 a 1 p 2 2 ,

..

n /p 1 a 1 p 2 a 2 ,

..

n/p 1 a 1 p 2 a 2 p 3 a 3 ...p k ,

..

n/p 1 a 1 p 2 a 2 p 3 a 3 ...p k a k -1。

那是最难的部分——如果你理解了这一点，你就完成了:) 现在只需总结来自测试的PRIME(n)运行时间和来自执行for循环的运行时间。后者总共贡献 (p 1 - 1)a 1 + (p 2 - 1)a 2 + .. + (p k - 1) ak，而第一部分贡献 n + n/p 1 + n/ p 1 2 + ... + n/p 1 a 1 p 2 a 2 p 3 a 3 ...p k a k -1. 如果不认真研究数论，就不可能评估这个和的渐近复杂度，但它比O(n!)（对于除数之和的上限，请参见此处）要好得多。

推荐阅读