带递归的大O

Question

我的 AP comp sic class 最近刚刚复习了 Big O 的一些基本排序算法。我对它如何与递归一起工作感到有点困惑，当我转到其他堆栈溢出答案时，我不太确定他们如何为递归函数的每个级别获得 n 的倍数并将它们添加到他们的最终答案中.

我想在我编的这个 class 中找到 node.nodeSortTest(int[] someArray) 的大 O 符号。我怎样才能得到答案？答案是什么？

public class node{

    public int value;

    public node higher = null;
    public node lower = null;

    //Making it a public static object was just easier for the test
    public static int addIndex = 0;

    public node(int i){
        value = i;
    }

    public void addToNode(int i){
        if(i>=value)
            if(higher != null) higher.addToNode(i);
            else higher = new node(i);
        else
            if(lower != null) lower.addToNode(i);
            else lower = new node(i);   
    }

    public static void nodeSortTest(int[] nums){
        if(nums.length<2)
            return;
        node keyNode = new node(nums[0]);
        for(int i = 1; i < nums.length; i++)
            keyNode.addToNode(nums[i]);
        node.addIndex = 0;
        keyNode.addTo(nums);
    }

    public void addTo(int[] nums){
        if(lower != null) lower.addTo(nums);
        nums[addIndex] = value;
        addIndex++;
        if(higher != null) higher.addTo(nums);
    }
}

Answer 1

复杂度通常有两个组成部分：

调用树的深度
每次调用中的迭代广度。

在这种情况下，您在每次递归调用时将问题大致分成两半：这使您进行了 log2(n) 次深度调用。

在每个级别，您处理数组的每个元素：深入研究代码以了解这是如何发生的；如果可以帮助您形象化作品，请使用纸和铅笔。这为该调用堆栈中的每个深度级别添加了一个 n 的因子。

结果是 David Choweller 已经给你的 n * log2(n) 复杂度。

Answer 2

我添加了一些代码来提示输入值 n 并计算对 n 随机整数数组的操作次数。测试似乎与 O(n log2n) 理论一致：

import java.util.Random;
import java.util.Scanner;

public class Node{

    public int value;

    public Node higher = null;
    public Node lower = null;

    //Making it a public static object was just easier for the test
    public static int addIndex = 0;
    public static int numOps = 0;

    public Node(int i){
        value = i;
    }

    public void addToNode(int i){
        if(i>=value)
            if(higher != null) higher.addToNode(i);
            else higher = new Node(i);
        else
            if(lower != null) lower.addToNode(i);
            else lower = new Node(i);
        numOps++;
    }

    public static void nodeSortTest(int[] nums){
        if(nums.length<2)
            return;
        Node keyNode = new Node(nums[0]);
        for(int i = 1; i < nums.length; i++)
            keyNode.addToNode(nums[i]);
        Node.addIndex = 0;
        keyNode.addTo(nums);
    }

    public void addTo(int[] nums){
        if(lower != null) lower.addTo(nums);
        nums[addIndex] = value;
        addIndex++;
        if(higher != null) higher.addTo(nums);
        numOps++;
    }
    public static void main(String args[]) {
        Random r = new Random();
        System.out.print("Enter size of array: ");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        int [] arrayToSort = new int [n];
        for (int i=0; i < n; i++) {
            arrayToSort[i] = r.nextInt(100000);
        }
        for (int i: arrayToSort) {
            System.out.print(i+",");
        }
        System.out.println();
        nodeSortTest(arrayToSort);
        for (int i:arrayToSort) {
            System.out.print(i+",");
        }
        System.out.println();
        System.out.println("\n\n\nn=" + arrayToSort.length + ", numOps=" + numOps);
        double log2n = Math.log(n)/Math.log(2);
        System.out.println("\n\nValue of n=" + n + " times log2n=" + log2n + " = " + n*log2n);
        scan.close();
    }
}

带递归的大O

Big O with recursion

java

sorting

recursion

big-o