Единственное достоверное сравнение - это кратчайшее время завершения работы на обычном оборудовании. Время завершения программы полностью зависит от оборудования, иначе какой смысл тратить деньги на более мощные машины?
Самое близкое, что вы можете получить к воспроизводимым результатам, это сообщить относительную скорость, например, предоставить пример программы и отчет о программе пользователя, работающей, скажем, в 50% случаев. Программа, которая в два раза быстрее на одном ПК, вероятно, будет в два раза быстрее на другом.
В универе мы будем отправлять задания, которые будут работать против «секретных» входов, однако мы могли бы отправлять несколько раз для исправления ошибок. Мое первое представление не работало вообще, но регистрировало все входные данные. ;)
РЕДАКТИРОВАТЬ: более длинный ответ.
Рассмотрим следующую программу
public class FibMain {
public static void main(String... args) {
{
long start = System.nanoTime();
System.out.println(iteration_fib(Integer.parseInt(args[0])));
long time = System.nanoTime() - start;
System.out.printf("Iteration took %,d us%n", time / 1000);
}
{
long start = System.nanoTime();
System.out.println(recursive_fib(Integer.parseInt(args[0])));
long time = System.nanoTime() - start;
System.out.printf("Recursion took %,d us%n", time / 1000);
}
}
public static long iteration_fib(int n) {
long t1 = 1;
long t2 = 1;
while (n-- > 2) {
long t = t2;
t2 += t1;
t1 = t;
}
return t2;
}
public static long recursive_fib(int n) {
if (n <= 2) return 1;
return recursive_fib(n - 1) + recursive_fib(n - 2);
}
}
Если вы посмотрите на сгенерированный байт-код с помощью javap -c, вы увидите
public static long iteration_fib(int);
Code:
0: lconst_1
1: lstore_1
2: lconst_1
3: lstore_3
4: iload_0
5: iinc 0, -1
8: iconst_2
9: if_icmple 25
12: lload_3
13: lstore 5
15: lload_3
16: lload_1
17: ladd
18: lstore_3
19: lload 5
21: lstore_1
22: goto 4
25: lload_3
26: lreturn
public static long recursive_fib(int);
Code:
0: iload_0
1: iconst_2
2: if_icmpgt 7
5: lconst_1
6: lreturn
7: iload_0
8: iconst_1
9: isub
10: invokestatic #13; //Method recursive_fib:(I)J
13: iload_0
14: iconst_2
15: isub
16: invokestatic #13; //Method recursive_fib:(I)J
19: ladd
20: lreturn
Итак, первый пример длиннее второго, так что вы можете заподозрить, что первый пример занимает больше времени. Тем не менее, вы были бы неверны для случаев, когда «n» - интересный размер.
Я запустил FibMain 44 на своей машине и получил следующий результат.
701408733
Iteration took 495 us
701408733
Recursion took 19,174,036 us
Это связано с тем, что время, необходимое для выполнения итерации, пропорционально n (в данном случае 44) и растет линейно, однако время, необходимое для рекурсии, пропорционально результату (в данном случае 701408733) и увеличивается экспоненциально.
Если вы введете 50 в качестве входных данных, то первое завершится за мгновение, второе займет столько времени, что мне надоело ждать.