Java 的复杂性

Question

我有一个关于我的代码复杂性的一般性问题。因为我正在做一些来自 Codeforces 的事情，所以复杂性对我来说很重要。问题集：https://codeforces.com/problemset/problem/1554/A

代码：

import java.util.Arrays; 
import java.util.List; 
import java.util.Scanner; 
import java.util.Collections;

public class main {
    public static void main(String[] args) {
        doCalculation();
    }

    public static void doCalculation () {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();

        for (int i = 0; i < n; i++) {
            int numbersInRow = sc.nextInt();
            long [] numbersToRead = new long[numbersInRow];
            for(int j = 0; j < numbersInRow; j++) {
                numbersToRead[j] = sc.nextLong();
            }

            long maxMultiplication = 0;

            for(int k = 0; k < numbersInRow; k++) {
                for (int m = k + 1; m < numbersInRow; m++) {
                    //Von jetzt an von 1 bis 2; von 1 bis 3; von 2 bis 3
                    long[] subarray = subArray(numbersToRead, k, m);
                    //System.out.println(Arrays.toString(subarray));

                    long min = Arrays.stream(subarray).min().getAsLong();
                    //System.out.println(min);

                    long max = Arrays.stream(subarray).max().getAsLong();
                    //System.out.println(max);

                    long multiplicationEveryArray = min * max;

                    if(multiplicationEveryArray > maxMultiplication) {
                        maxMultiplication = multiplicationEveryArray;
                    }
                }
            }
            System.out.println(maxMultiplication);
        }
    }
    
    public static long[] subArray(long[] array, int beg, int end) {
        return Arrays.copyOfRange(array, beg, end + 1);
    } 
}

我认为 copyRange 的复杂度为 O(n)，而 subarry 的复杂度相同。有哪些方法可以在不采用不同方法的情况下提高我的复杂性？

Answer 1

此代码存在多个问题：

我认为您对这个问题使用了过多的 space。在这个问题中，为什么你总是在找出最大值和最小值之前创建一个新数组。而且这也是一个循环，所以以后肯定会导致内存问题。因为大约 space 复杂度将超过 O(n2)

long[] subarray = subArray(numbersToRead, k, m);
long min = Arrays.stream(subarray).min().getAsLong();
long max = Arrays.stream(subarray).max().getAsLong();

首先你要在 3n 时间内完成所有这些（复制 O(n) + O(n) 寻找最小值，O(n) 寻找最大值）

我建议如果可能的话找一个更好的算法，如果可能的话可以在 O(n) 时间内找到最大值和最小值。

如果那不可能，请尝试在单个循环中找到 maximum 和 minimum 并尝试避免使用您的这个函数。

public static long[] subArray(long[] array, int beg, int end) {
    return Arrays.copyOfRange(array, beg, end + 1);
}

与其每次都创建一个新数组，不如尝试迭代同一个数组。如果您没有任何可以在不创建新数组的情况下迭代原始数组的函数，请避免使用流，尽管我对此表示怀疑，情况确实如此。我认为有某种函数可以帮助限制在数组的某个范围内找到最小值和最大值

类似于：

Arrays.stream(numbersToRead).range(k, m)

Answer 2

通常，这些问题的设置方式是暴力方法将在一百万年内完成。

看着这些例子，我的第一直觉是你只需要查看相邻的数字，这就成了一个复杂度为 O(n) 的问题。

如果你有f(1,2)和f(2,3)那么f(1,3)肯定是f(1,2)和f(2,3)中的最大值。第一个和最后一个元素的乘积不可能是最大值，因为这意味着它们中至少有一个必须小于或等于中间的第二个元素才能被考虑，使得乘积小于或等于“只是邻居”的产物。

你可以继续通过归纳得出 f(1,n+1) 将是 max(f(1,2), f(2,3), ... f(n,n+1)) 的结论。

为了摆脱 O(n^2) 循环尝试

for(int k = 0; k < numbersInRow - 1; k++) {
  final int product = numbersToRead[k] * numbersToRead[k+1];
  if (product > maxMultiplication) {
    maxMultiplication = product;
  }
}

Java 的复杂性

Complexity in Java

java

arrays

time-complexity

complexity-theory