Given two positive integers m, n o their greatest common factor:
E1: with n m, get the remainder r,
E2: if r=0, the algorithm is terminated, n is the answer
Assumed known m=119 and n=544, we start from E1, in this case, with n by m is very simple, because business is 0, the remainder is 119, then r=119, we entered the steps E2, because r indicates a 0, and five operations, in step E3, we set m=544, n=119, it is obvious that if the original m
According to the passage, the Java code below
/* *
* Archimedes algorithm*
* @ the author I TM handsome detonation
* @ date 2020/6/22 thus
* @ week Monday*/
Public class Archimedes {
Public static void main (String [] args) {
Algorithm1 ();
Algorithm2 ();
}
/* *
* calculation 1
*/
Private static void algorithm1 () {
Long startTime=System. NanoTime ();//get the starting time of the algorithm, the nanosecond timestamps
Int m=119;
Int n=544;
Int r;//remainder
Do {
R=m % n;
M=n;
N=r;
} while (r!=0);
System. The out. Println (" algorithm 1: "+ (System. NanoTime () - startTime));//output algorithm run much time
}
/* *
* calculation 2
*/
Private static void algorithm2 () {
Long startTime=System. NanoTime ();//get the starting time of the algorithm, the nanosecond timestamps
Int m=119;
Int n=544;
If (m & lt; N) {
//exchange values of m and n
Int sun=n;
N=m;
M=sun;
}
Int r;//remainder
Do {
R=m % n;
M=n;
N=r;
} while (r!=0);
System. The out. Println (" algorithm 2: "+ (System. NanoTime () - startTime));//output algorithm run much time
}
}
Two calculation way eventually run by time (ns) :
Algorithm sons 700
Algorithm 2:55 00
Why do I feel 2 steps obviously than algorithm 1 complex, operation time is so much less than algorithm 1
CodePudding user response:
Top themselves and went outCodePudding user response:
You added a count to the two algorithms while loop look each count how many times they withdraw more than % seeAlgorithm 1 did take more than 5 times,
Algorithm 2 did more than 4 times take
Time difference mainly here
In addition, in fact not so big gap between the two algorithms of timeliness
Because the program has just started will also take a system resources
You algorithm 1 and 2 of the order of execution, in turn, will find that instead of algorithm 2 is more time-consuming
Timeliness, do you really want to test for at least two algorithm combined with loop, the running more than 100000 times
To see the real gap
Actually small gap
Algorithm 1: don't need data numerical comparison, but more to do more than one take
Algorithm 2: made a numerical comparison more and do less take over at a time
CodePudding user response:
I make two algorithms run ten million times eachResults total time:
Algorithm 1 is about 1.5 times the time-consuming
2There is absolutely no 10 times the gap so much
This example can prove that:
Take more computing time consuming than numerical comparison