BinarySearchTree搜索速度效率

import java.io.FileWriter; 
import java.io.IOException; 
import java.io.PrintWriter; 
import java.util.Random; 


public class BSTSearchTimer { 

int [] n = {10000, 50000, 100000, 250000}; 
Random rand = new Random(); 

public static void main(String[] args) throws IOException{ 

    BSTSearchTimer timer = new BSTSearchTimer(); 
    timer.runBSTSearchTimer(); 

} 

public void runBSTSearchTimer() throws IOException{ 
    PrintWriter out = new PrintWriter(new FileWriter("tree2.csv")); 
    int reps = 10000; // the number of searches that we will do on the tree 


    for (int i = 0; i < n.length; i++){ 
     BinarySearchTree<Long> longBST = new BinarySearchTree<Long>(); 
     boolean success = true; 

     int numOfElements = n[i]; 

     while (longBST.size() < numOfElements){ 

       success = longBST.add(rand.nextLong()); 
       while (!success){ // should keep attempting to add values until success is true 
        success = longBST.add(rand.nextLong()); 
      } 

     } 

     long start = System.currentTimeMillis(); // start the timer for searching 

     for (int j = 0; j < reps; j++){ // search rep times 
      longBST.find(rand.nextLong()); 
     } 
     long end = System.currentTimeMillis(); // end timer for searching tree 

     double time = end-start; 

     System.out.printf("%d, %f\n", longBST.size(), time); 
     out.printf("%d, %f\n", n[i], time); 

    } 
    out.close(); 
} 
}

当我运行这个程序，它是应该做4个不同大小的树：10000，50000，100000，250000我知道，在搜索BSTS速度效率应该是O（日志做万个搜索时BinarySearchTree搜索速度效率

我得到这些数字：N），但我得到这些数字（第一列是树的大小，二是它采取做搜索）

10000, 9.000000 
50000, 3.000000 
100000, 4.000000

时间当进行100,000次搜索时：

10000, 41.000000 
50000, 31.000000 
100000, 40.000000 
250000, 74.000000

任何提示将不胜感激。

来源

2011-05-15 Optimum

很可能你会看到“未命中”的效果。由于您只是搜索随机数字，因此不在树中的数字将比需要的数字长得多。

另外，二叉搜索树的效率是O（h），其中h是树的高度。 Red-Black trees和AVL trees保证它们将以O（log n）的高度构建，但随机构建的树可能容易以高度接近O（n）结束。

来源

2011-05-15 15:34:47 dlev

这实际上是有道理的。我现在明白了。谢谢你的提示。我真的很想知道为什么这段代码产生了我认为是随机数的东西。但是我搜索随机数的事实可能会导致很多不同的结果。谢谢！ – Optimum 2011-05-15 15:57:27

BinarySearchTree搜索速度效率

回答

相关问题