java - 给定算法分析的"main"java.lang.StackOverflowError

Question

我知道这个问题已经被问了很多，但我无法弄清楚我的问题。

我正在尝试获取时间复杂度，但出现此错误:线程“main”中的异常 java.lang.StackOverflowError 在 MedianAlgorithm2.Select(MedianAlgorithm2.java:22)

当我传递数组大小> 100000时。

递归选择方法如下:

public static int Select(int[] A, int l, int m, long h) {   
    int pos = Partition(A, l, h);
    if (pos == m) {
        return A[pos];
    }
    if (pos > m) {
        return Select(A, l, m, pos - 1);
    }
    if (pos < m) {
        return Select(A, pos + 1, m, h); // this is line 22 mentiond in exception
    }
    return 0;
}

public static int Partition(int[] A, int l, long h) {
    int pivotval = A[l];
    int pivotloc = l;   
    for (int j = l+1; j <= h; j++) {
        if (A[j] < pivotval) {
            pivotloc = pivotloc + 1;
            int temp = A[pivotloc];
            A[pivotloc] = A[j];
            A[j] = temp;
        }
    }
    int temp = A[l];
    A[l] = A[pivotloc];
    A[pivotloc] = temp;
    return pivotloc;
}

我已将 h 从 int 更改为 long，但仍然收到错误

谢谢。

Answer 1

您的 JVM 内存不足。您只需分配更多即可。