Javaでハノイの塔の問題をテストしていたところ、次のコードを実行しました:(便宜上削除しました)sysouts
public class Util {
public static void main(String[] args) {
for (int i = 1; i <= 30; i++) {
long startTime = System.currentTimeMillis();
solveTowerOfHanoi(i, "A", "B", "C");
System.out.println("Time taken for " + i + ": "
+ (System.currentTimeMillis() - startTime));
}
}
public static void solveTowerOfHanoi(int n, String src, String inter,
String dest) {
if (n == 0) {
return;
}
solveTowerOfHanoi(n - 1, src, dest, inter);
solveTowerOfHanoi(n - 1, inter, src, dest);
}
}
私は実験を行い、1 から 35 までのディスク サイズ (インデックス) を試しました。非常に奇妙なタイミング パターンを観察しました。プログラムの出力は次のとおりです。
Time taken for 1: 0
Time taken for 2: 0
Time taken for 3: 0
Time taken for 4: 0
Time taken for 5: 0
Time taken for 6: 0
Time taken for 7: 0
Time taken for 8: 1
Time taken for 9: 0
Time taken for 10: 0
Time taken for 11: 0
Time taken for 12: 0
Time taken for 13: 0
Time taken for 14: 0
Time taken for 15: 0
Time taken for 16: 0
Time taken for 17: 0
Time taken for 18: 3
Time taken for 19: 2
Time taken for 20: 11
Time taken for 21: 10
Time taken for 22: 39
Time taken for 23: 37
Time taken for 24: 158
Time taken for 25: 147
Time taken for 26: 603
Time taken for 27: 579
Time taken for 28: 2414
Time taken for 29: 2304
Time taken for 30: 9509
Time taken for 31: 9408
Time taken for 32: 38566
Time taken for 33: 37531
Time taken for 34: 152255
Time taken for 35: 148704
質問 1 : アルゴリズムには指数関数的な増加(2^n-1)があります。しかし、その後、20 から 35 へと急上昇したのでしょうか。
質問 2 : また、私をさらに驚かせたもう 1 つのことは、ペアの時間が等しいことです。19 から始めて、(19,20)、(21,22)、(23,24)、(25,26) など....同等の時間があります。アルゴリズムの成長率が実際に指数関数的である場合、なぜ2つのインデックスがほぼ同等の時間を与え、次のインデックスで突然ジャンプするのか理解できませんか?
注: このプログラムを 2 ～ 3 回繰り返したところ、ほぼ同等のタイミングが得られたので、平均的な実行と見なすことができます。
編集
して、次の
結果System.nanoTime()を得ました：
Time taken for 1: 62644
Time taken for 2: 3500
Time taken for 3: 3500
Time taken for 4: 4200
Time taken for 5: 6300
Time taken for 6: 7350
Time taken for 7: 11549
Time taken for 8: 19948
Time taken for 9: 47245
Time taken for 10: 73142
Time taken for 11: 87491
Time taken for 12: 40246
Time taken for 13: 39196
Time taken for 14: 156784
Time taken for 15: 249875
Time taken for 16: 593541
Time taken for 17: 577092
Time taken for 18: 2318166
Time taken for 19: 2305217
Time taken for 20: 9468995
Time taken for 21: 9082284
Time taken for 22: 37747543
Time taken for 23: 37230646
Time taken for 24: 150416580
Time taken for 25: 145795297
Time taken for 26: 603730414
Time taken for 27: 578825875
Time taken for 28: 2409932558
Time taken for 29: 2399318129
Time taken for 30: 9777009489
出力はミリ秒にほぼ似ていますが、全体像を明確にしています...私の質問 1の答えかもしれませんが、質問 2はまだ興味深いものです。そして、System.nanoTime()もう1つの質問を提起しました：
質問 3 : インデックス 1 が次のインデックス (2、3...) などよりも時間がかかるのはなぜですか?