java - 大 O 与递归

Question

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

我想在我编写的这个类中找到 node.nodeSortTest(int[] someArray) 的 Big-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

我添加了一些代码来提示输入 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();
    }
}