package ch02;
import java.util.Arrays;
import java.util.Random;
/**
* 练习2.8 假设需要生成前N个整数的一个随机转换。例如{4，3，1，5，2}和{3，1，4，2，5}就是合法的转换，但
* {5，4，1，2，1}则不是，因为数1出现两次而数3却没有。这个程序常常用于模拟一些算法。我们假设存在一个随机数
* 生成器r,它有方法randInt(i, j),它以相同的概率生成i和j之间的整数。下面是三个算法：
* 1. 如下填入从a[0]到a[n-1]的数组a;为了填入a[i],生成随机数直到它不同于已经生成的a[0],a[1],...,a[i-1]时
* 再将其填入a[i]。
* 2. 同算法（1），但是要保存一个附加的数组，称之为used数组。当一个随机数ran最初被放入数组a的时候，置used[ran]=true。
* 这就是说，当用一个随机数填入a[i]时，可以用一步来测试是否该随机数已经被使用，而不是像第一个算法那样（可能）用
* i步测试。
* 3. 填写该数组使得a[i] = i + 1。然后
* for (i = 1; i < n; i++)
* swapReference(a[i], a[randInt(0, i)]);
* a. 证明这三个算法都生成合法的置换，并且所有的置换都是可能的。
* （证明略。）
* b. 对每一个算法给出你能够得到的尽可能准确的期望运行时间分析（用大O)。
* c. 分别写出程序来执行每个算法10次，得出一个好的平均值。对N=250, 500, 1000, 2000运行程序（1）；
* 对N=25 000, 50 000, 100 000, 200 000, 400 000, 800 000运行程序（2）；对N=100 000, 200 000, 400 000, 800 000,
* 1600 000, 3 200 000, 6 400 000运行程序（3）；
* d. 将实际的运行时间与你的分析进行比较。
* e. 每个算法的最坏情形的运行时间是什么？
*
*/
public class EX08 {
static final Random rand = new Random(47);
private static int randInt(int i, int j) {
return rand.nextInt(j-i+1) + i;
}
/**
* 如下填入从a[0]到a[n-1]的数组a;为了填入a[i],生成随机数直到它不同于已经生成的a[0],a[1],...,a[i-1]时
* 再将其填入a[i].
* 下面算法1和算法2的时间复杂度是从标准答案中参考的，因为涉及概率问题，本人不太肯定。
* 期望运行时间 O(N^2 * logN)。
* 最坏运行时间 O(N^2 * logN)。
*/
public static int[] algorithm1(int N) {
int []a = new int[N];
for (int i = 0; i < a.length; ++i) {
while (true) {
a[i] = randInt(1, N);
boolean foundDup = false;
for (int j = 0; j < i; ++j) {
if (a[i] == a[j]) {
foundDup = true;
break;
}
}
if (!foundDup) {
break;
}
}
}
return a;
}
/**
* 同算法（1），但是要保存一个附加的数组，称之为used数组。当一个随机数ran最初被放入数组a的时候，置used[ran]=true。
* 这就是说，当用一个随机数填入a[i]时，可以用一步来测试是否该随机数已经被使用，而不是像第一个算法那样（可能）用
* i步测试。
* 期望运行时间O(N * logN)。
* 最坏运行时间O(N * logN)。
*/
public static int[] algorithm2(int N) {
int[] a = new int[N];
boolean[] used = new boolean[N+1];
for (int i = 0; i < a.length; ++i) {
do {
a[i] = randInt(1, N);
} while (used[a[i]]);
used[a[i]] = true;
}
return a;
}
/**
* 填写该数组使得a[i] = i + 1。然后
* for (i = 1; i < n; i++)
* swapReference(a[i], a[randInt(0, i)]);
* 期望运行时间O(N)。
* 最坏运行时间O(N)。
*/
public static int[] algorithm3(int N) {
int[] a = new int[N];
for (int i = 0; i < N; ++i) {
a[i] = i + 1;
}
for (int i = 1; i < N; ++i) {
swapReferences(a, i, randInt(0, i));
}
return a;
}
private static void swapReferences(int a[], int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
/*System.out.println(Arrays.toString(algorithm1(10)));
System.out.println(Arrays.toString(algorithm2(10)));
System.out.println(Arrays.toString(algorithm3(10)));*/
int []N1 = new int[] {250, 500, 1000, 2000};
int []N2 = new int[] {25000, 50000, 100000, 200000, 400000, 800000};
int []N3 = new int[] {100000, 200000, 400000, 800000, 1600000, 3200000, 6400000};
System.out.println("算法1:");
for (int i = 0; i < N1.length; ++i) {
System.out.println(N1[i] + ": " + testN(1, N1[i]) + " ms");
}
System.out.println("算法2:");
for (int i = 0; i < N2.length; ++i) {
System.out.println(N2[i] + ": " + testN(2, N2[i]) + " ms");
}
System.out.println("算法3:");
for (int i = 0; i < N3.length; ++i) {
System.out.println(N3[i] + ": " + testN(3, N3[i]) + " ms");
}
}
private static long testN(int algorithmNum, int N) {
long startTime = System.currentTimeMillis();
switch (algorithmNum) {
case 1:
for (int i = 0; i < 10; ++i)
algorithm1(N);
break;
case 2:
for (int i = 0; i < 10; ++i)
algorithm2(N);
break;
default:
for (int i = 0; i < 10; ++i)
algorithm3(N);
break;
}
long endTime = System.currentTimeMillis();
return endTime - startTime;
}
}
/*
* 算法时间分析
* 如果算法的复杂度为O(N^k), k>1, 如果输入分别为 N1, N2,且N1的运行时间为T1,则
* T2 = T1 * ((N2/N1)^k) * (logN2/logN1)。可以验证下面的执行时间是否大致符合此规律。
* 下面的算法1和算法2的时间，不太肯定，大概正确。
* 算法1: O(N^2 * logN)
* N 实际时间(ms) 预估时间(ms)
* 250 4 --
* 500 11
* 1000 48
* 2000 206
*
* 算法2: O(N*logN)
* N 实际时间(ms) 预估时间(ms)
* 25k 75 --
* 50k 140
* 100k 298
* 200k 601
* 400k 1325
* 800k 3052
*
* 算法3: O(N)
* N 实际时间(ms) 预估时间(ms)
* 100k 26 ---
* 200k 51 52
* 400k 107 102
* 800k 245 214
* 160m 754 490
* 320m 1927 1508
* 640m 4587 3854
*
* 总结：因为忽略了常数系数，所以复杂度都是正确的。
* */
