分析一道 Leetcode 题“974. 子数组和可被 K 整除”的时间复杂度

Question

我想出了一个算法来解决这个问题。但是我不确定这个解决方案的时间复杂度到底是多少。是 O(n^3) 还是 O(n^2) 。我想知道给定函数 subarraysDivByK 的时间复杂度是多少？请帮忙

{
    public int subarraysDivByK(int[] A, int K) 
    {
        int n = A.length;
        int count = 0;
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
            {
                int sumWindow = findSum(A,i,j);
                if(sumWindow%K==0)
                {
                    count++;
                }
            }
        }
        return count;
    }
    
    public int findSum(int[] a, int start, int end)
    {
        int sum = 0;
        for(int i = start;i<=end;i++)
        {
            sum = sum + a[i];
        }
        return sum;
    }
}

Answer 1

对于 i 的某些值，您将尝试 j 从 i 到 n 的所有值。对于每个 j，您将计算 j-i 个元素的总和。为此，您需要 O(0 + 1 + ... + (n-i))=O((n-i)^2) 操作。因此，对于 i 的所有可能值，您需要 O(n^2 + (n-1)^2 + ... + 2^2 + 1^2) = O(n^3) 操作。答案：O(n^3).

分析一道 Leetcode 题“974. 子数组和可被 K 整除”的时间复杂度

Analysing the time complexity of a Leetcode problem "974. Subarray Sums Divisible by K"

java

algorithm

time-complexity