algorithm - Codility CommonPrimeDivisors 时间复杂度？

问题描述

关于 Codility 中的Common Prime Divisors任务，我有几个时间复杂度问题。问题如下：

素数是一个正整数 X，它正好有两个不同的除数：1 和 X。前几个素数是 2、3、5、7、11 和 13。

如果存在正整数 K 使得 D * K = P，则素数 D 称为正整数 P 的素数除数。例如，2 和 5 是 20 的素数除数。

给定两个正整数 N 和 M。目标是检查整数 N 和 M 的素数因数集是否完全相同。

例如，给定：

N = 15 和 M = 75，质数除数相同：{3, 5}；

N = 10 和 M = 30，质数除数不同：{2, 5} 不等于 {2, 3, 5}；

N = 9 和 M = 5，主要因数不相同：{3} 不等于 {5}。

写一个函数：
class Solution { public int solution(int[] A, int[] B); }
即，给定两个由 Z 整数组成的非空数组 A 和 B，返回 A[K] 和 B[K] 的素数除数完全相同的位置 K 的数量。

例如，给定：
A[0] = 15   B[0] = 75
A[1] = 10   B[1] = 30
A[2] = 3    B[2] = 5
该函数应返回 1，因为只有一对 (15, 75) 具有相同的素数除数集。

为以下假设编写一个有效的算法：

Z 是 [1..6,000] 范围内的整数；数组 A 的每个元素，

B 是 [1..2,147,483,647] 范围内的整数。

我设法使用以下算法100％解决它：

class Solution {
    public int solution(int A[], int B[]) {
        int result = 0;

        for (int i = 0; i < A.length; i++){

            int gcdOfAAndB = gcd(A[i], B[i]);

            if (
                factorsOfRemainderAreTheSameOfGCD(A[i], gcdOfAAndB) &&
                factorsOfRemainderAreTheSameOfGCD(B[i], gcdOfAAndB)
            ) {
                result++;
            }

        }

        return result;
    }

    public boolean factorsOfRemainderAreTheSameOfGCD(int input, int gcdOfAAndB) {
        int factorsNotInGCD = input / gcdOfAAndB;

        while (gcdOfAAndB % factorsNotInGCD != 0){

            int gcd = gcd(gcdOfAAndB, factorsNotInGCD);

            if (gcd == 1)
                return false;

            factorsNotInGCD /= gcd;

        }

        return true;
    }

    public int gcd(int a, int b) {
        if (a % b == 0){
            return b;
        }

        return gcd(b, a % b);
    }
}

我假设算法的时间复杂度为：

O(Z * (log(log(M+N)+N) * log(N) + log(log(M+N)+M) * log(M)))，因为：

while 循环内的 GCD 以 ; 的方式执行log(log(M+N)+input)。
while 循环本身显然具有对数增长率：factorsNotInGCD 在每次迭代中至少减半；
因此我得出结论，它们结合起来代表log(log(M+N)+input) * log(input)；
由于 while 循环执行了两次，一次用于 N 和 M，我们将它们相加得到(log(log(M+N)+N) * log(N) + log(log(M+N)+M) * log(M)；
最后，Z 表示将要测试的 N 和 M 的数量。

我的问题：

我对算法时间复杂度的假设是否正确？如果不是，那么正确的时间复杂度是多少？
Codility 说它检测到时间复杂度是O(Z * log(max(A) + max(B))**2)，我想知道如何实现。

非常感谢提前

标签： algorithmprimesprime-factoring

algorithm - Codility CommonPrimeDivisors 时间复杂度？

问题描述

解决方案

推荐阅读