``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 ``` ```package algs32.kdtree; import algs12.Point2D; import algs13.Queue; import stdlib.*; /* * If the output looks like this, then you have a bug! * * 500: kd=0.146000 brute=0.021000 * 1000: kd=0.034000 brute=0.015000 * 2000: kd=0.052000 brute=0.032000 * 4000: kd=0.082000 brute=0.053000 * 8000: kd=0.175000 brute=0.108000 * 16000: kd=0.308000 brute=0.224000 * 32000: kd=0.649000 brute=0.508000 * 64000: kd=1.329000 brute=2.123000 * 128000: kd=3.375000 brute=4.144000 * 256000: kd=7.147000 brute=10.214000 * 512000: kd=18.383000 brute=26.161000 * * Output should look like this: * * 500: kd=0.054000 brute=0.026000 * 1000: kd=0.036000 brute=0.018000 * 2000: kd=0.008000 brute=0.038000 * 4000: kd=0.011000 brute=0.063000 * 8000: kd=0.013000 brute=0.178000 * 16000: kd=0.019000 brute=0.274000 * 32000: kd=0.037000 brute=0.895000 * 64000: kd=0.050000 brute=2.099000 * 128000: kd=0.089000 brute=4.416000 * 256000: kd=0.082000 brute=10.716000 * 512000: kd=3.682000 brute=27.141000 * * This is also okay: * * 500: kd=0.002000 brute=0.033000 * 1000: kd=0.001000 brute=0.014000 * 2000: kd=0.000000 brute=0.034000 * 4000: kd=0.000000 brute=0.098000 * 8000: kd=0.000000 brute=0.197000 * 16000: kd=0.001000 brute=0.407000 * 32000: kd=0.000000 brute=1.654000 * 64000: kd=0.000000 brute=3.241000 * 128000: kd=0.000000 brute=6.194000 * 256000: kd=0.000000 brute=13.980000 */ public class NearestNeighborPerformanceTest { static int NUM_SIZES = 11; public static void main(String[] args) { Queue queue = new Queue<> (); for (int i=0; i<1000; i++) queue.enqueue(new Point2D(Math.random(), Math.random())); int N = 250; for (int count=1; count