计算和改进时间和内存复杂性（Java）

private static int Sum (int[] a, int from, int to){
    int total=0;
    for (int i=from; i <= to; i++)
        res += a[i];
    return total;
}

public static int Method3 (int []a){
    int temp=0;
    for (int i=0; i <= a.length; i++)
    {
        for (int j=0; j <= a.length; j++)
        {
            int c = Sum(a,i,j);
            if (c%3 == 0)
            {
                if (j-i+1 > temp)
                temp = j-i+1;
             }
         }
    }
    return temp;
}

The purpose of Method3 method is finding the longest combination of a given array numbers' , so that the sum of the numbers of the combination can be divided by 3 without remainder. I'm now trying to figure out the time and memory complexity of the Method3 method , and then my purpose is to learn how to improve it to the maximum.

Method3方法的目的是找到给定数组'的最长组合,以便组合数的总和可以除以3而没有余数。我现在正试图弄清楚Method3方法的时间和内存复杂性,然后我的目的是学习如何最大限度地提高它。

My assumption is : the first two loops in Method3 result in time complexity of O(n^2) because it's repeated (n + (n-1) + ... +1) times , which equals to [n(n+1)]/2 => (1/2)n^2+(1/2)n => O(n^2). BUT, we also have the Sum method, which is nested within both of the loops in Method3, and its worst-case complexity can only be O(n) - since it's the biggest possible gap between i and j(or a.length in other words) So therefore , I think the final time complexity for Method3 is : n^2 * n = n^3. Is that right? Now , regarding memory complexity , I'm really confused. My assumption is that it's O(1), because there are only integer variable in this program ,that hold one field.

我的假设是:Method3中的前两个循环导致O(n ^ 2)的时间复杂度,因为它重复(n +(n-1)+ ... +1)次,等于[n(n + 1) )] / 2 =>(1/2)n ^ 2 +(1/2)n => O(n ^ 2)。但是,我们还有Sum方法,它嵌套在Method3的两个循环中,并且它的最坏情况复杂度只能是O(n) - 因为它是i和j之间最大可能的间隙(或者a.length in因此,我认为Method3的最终时间复杂度为:n ^ 2 * n = n ^ 3。是对的吗?现在,关于内存复杂性,我真的很困惑。我的假设是它是O(1),因为在这个程序中只有整数变量,它包含一个字段。

Now the next question, how do I make it more efficient? How do I even approach to something like this? and finally, how can I know that the complexity I've reached is the best possible?

现在接下来的问题是,如何提高效率呢?我怎么能接近这样的事情呢?最后,我怎么知道我达到的复杂性是最好的?

Thanks!

1 个解决方案

#1

Yes, time complexity is O(n^3). And yes, space complexity is O(1). The only space used is constant number of indices.

是的,时间复杂度是O(n ^ 3)。是的,空间复杂度是O(1)。使用的唯一空间是常数索引。

A way to make your algorithm more efficient and shorten the amount of comparisons is to reverse your inside for loop. Right now, you are basically checking every possible combination of i and j. For example, for indices 1, 2, 3, 4. you are checking 1-2, 1-3, 1-4, 2-3, 2-4, 3-4.

一种使您的算法更有效并缩短比较量的方法是反转内部for循环。现在,您基本上检查i和j的每个可能组合。例如,对于索引1,2,3,4,您将检查1-2,1-3,1-4,2-3,2-4,3-4。

Instead, you can start with j = a.length()-1. That way, you are starting with the 'longest combination' with your current i. As soon as a combination works (meaning if the combination satisfies the Sum(1, i, j)%3 == 0 requirement), you don't have to check all the other j values, and you can jump to the next i value.

相反,你可以从j = a.length() - 1开始。这样,你开始与你当前的'最长的组合'。一旦组合起作用(意味着如果组合满足Sum(1,i,j)%3 == 0要求),则不必检查所有其他j值,并且您可以跳转到下一个i值。

Your Sum method is fine the way it is.

你的Sum方法很好。

EDIT:

The result is still going to be an O(n^3) worst case time complexity. but in reality, can it potentially make your code faster? Yes.(definitely) Since you have three iterations, the worst case is always going to be N^3, though.

结果仍然是O(n ^ 3)最坏情况时间复杂度。但实际上,它是否可能使您的代码更快?是的。(绝对)由于你有三次迭代,最坏的情况总是会是N ^ 3。

#1