遞歸的大O

Question

我最近剛剛通過一些基本的排序算法對AP進行了一次簡單的介紹。我有點困惑，但它如何與遞歸一起工作，當我去其他堆棧溢出的答案時，我不太確定他們如何得到他們的遞歸函數的每個級別的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並計算隨機整數數組上的操作數。測試似乎與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(); 
    } 
} 

Answer 2

我們通常有兩種成分的複雜性：

1. 調用樹
2. 廣度每次調用迭代的深度。

在這種情況下，您在每次遞歸調用時將問題大致分爲兩部分：這會給您深度的log2（n）調用。

在每個級別上，您都會處理數組中的每個元素：挖掘代碼以查看發生的方式;使用紙和鉛筆如果可以幫助你看到作品。這爲調用堆棧中的每個深度級別添加了因子n。

結果是David Choweller給你的n * log2（n）複雜度。