java - 递归算法的大O复杂度

Question

我有一个用于计算加权中位数的递归算法。我试图弄清楚 Big-O 时间复杂度是多少，但我有点卡住了。有人能帮助我吗。谢谢大家的帮助。 JAVA代码如下:

public static double WeightedMedian(ArrayList<Double> a1, ArrayList<Double> a2, int p, int r) {
if (r == p) {
    return a1.get(p);
}

if (r-p == 0) {
    if (a2.get(p) == a2.get(r)) {
        return (a1.get(p) + a1.get(r))/2;
    }
    if (a2.get(p) > a2.get(r)) {
        return a1.get(p);
    } else {
        return a1.get(r);}
    }

    long q = partition(a1, p, r);  
    double wl=0,wg=0;
    for (int i=p; i<=q-1; i++) {
        wl += a2.get(i);
    }
    for (int i=(int) (q+1); i<=r; i++) {
        wg += a2.get(i);
    }
    if (wl<0.5 && wg<0.5) { 
        return a1.get((int)q);
    } else {
    if (wl > wg) { 
        double x = a2.get((int)q) + wg;
        a2.set((int) q,x);
        return WeightedMedian(a1,a2, p+1, (int)q);
    } else { 
       double x = a2.get((int)q) + wl;
       a2.set((int) q,x);
       return WeightedMedian(a1, a2, (int)q, r);
    }
}

抱歉，这是我第一次在这里发帖，所以我不太好，我尝试更好地格式化代码，但它一直在奇怪的地方等。无论如何，分区代码如下:

 public static long partition (ArrayList<Double> arr, int low, int high)
{
    double pivot = arr.get(high);

    int i = low - 1;

    for (int j = low; j <= high- 1; j++)
    {
        if (arr.get(j) <= pivot)
        {
            i++;
            double temp = arr.get(i);
            arr.set(i,arr.get(j));
            arr.set(j,temp);
        }
    }
    double temp1 = arr.get(i + 1);
    arr.set(i + 1, arr.get(high));
    arr.set(high,temp1);

    return i + 1;
}

Mathematical description of weighted median

Answer 1

public static double WeightedMedian(ArrayList<Double> a1, ArrayList<Double> a2, int p, int r) {
if (r == p) {
    return a1.get(p); //O(1)
}

if (r-p == 0) {
    if (a2.get(p) == a2.get(r)) { //O(1) + O(1)
        return (a1.get(p) + a1.get(r))/2; //O(1) + O(1)
}
if (a2.get(p) > a2.get(r)) { //O(1) + O(1)
    return a1.get(p); //O(1)
} else {
    return a1.get(r);} //O(1)
}

long q = partition(a1, p, r);  
double wl=0,wg=0;
for (int i=p; i<=q-1; i++) { //O(n)
    wl += a2.get(i); 
}
for (int i=(int) (q+1); i<=r; i++) { //O(n)
    wg += a2.get(i); 
}
if (wl<0.5 && wg<0.5) { 
    return a1.get((int)q); //O(1)
} else {
    if (wl > wg) { 
        double x = a2.get((int)q) + wg; //O(1)
        a2.set((int) q,x); //O(1)
        return WeightedMedian(a1,a2, p+1, (int)q);
    } else { 
       double x = a2.get((int)q) + wl; //O(1)
       a2.set((int) q,x); //O(1)
       return WeightedMedian(a1, a2, (int)q, r);
    }
}

所以上面的方法是O(n)，由O(1)...+O(n) = O(n)

public static long partition (ArrayList<Double> arr, int low, int high)  {
double pivot = arr.get(high); //O(1)

int i = low - 1;

for (int j = low; j <= high- 1; j++) //O(n)
{
    if (arr.get(j) <= pivot) //O(1)
    {
        i++;
        double temp = arr.get(i); //O(1)
        arr.set(i,arr.get(j)); //O(1)
        arr.set(j,temp); //O(1)
    }
}
double temp1 = arr.get(i + 1); //O(1)
arr.set(i + 1, arr.get(high)); //O(1)
arr.set(high,temp1); //O(1)

return i + 1;
}

而上面的方法“划分”，也是O(n)，由O(1)... + O(n)导出

所以，O(n)，因为 arraylist 是通过索引直接访问，所有获取/设置都是 O(1)，所有循环都是 O(n)