我想出了一個演算法來解決這個問題。但是我不確定這個解決方案的時間復雜度到底是什么。是 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;
}
}
uj5u.com熱心網友回復：
對于某些值，i您將嘗試j從ito 的所有值n。對于每個，j您將計算j-i元素的總和。為此，您將需要 O(0 1 ... (ni))=O((ni)^2) 次操作。所以對于所有可能的值，i你需要 O(n^2 (n-1)^2 ... 2^2 1^2) = O(n^3) 操作。答案：O(n^3)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/344356.html
下一篇：盜屋變種：最多可盜K間屋