11
How to determine the best choice between these two functions for implementation?
1:
int X(int x){
if(x<=0)
return 0;
return(x + X(x-1));
}
2:
int Y(int x){
int soma=0;
for(int i=0;i<=x;++i)
soma+=i;
return soma;
}
How to determine the complexity equations and solve them? Or is there another method?
10
Overall, responses so far address the measurement of efficiency in practical terms.
I will give you an answer in theoretical terms, since you ask two questions: How to determine the equations of complexity and whether there is another method.
To answer the first question, first of all I recommend an introductory book of algorithms that teaches Big-O notation.
The books I recommend are:
I’m going to reduce the analysis on kids, not rigorously, without involving loop invariants, etc..
First the easiest to analyze, case 2.
This case consists of only one loop that repeats an O(1) complexity operation. The number of repetitions is directly proportional to the function input value. If the argument x for N, then the loop will be repeated N times. Apart from the loop, the body of the function only has other complexity operations O(1):
int Y(int x) { // O(1)
int soma=0; // O(1)
// O(1) O(1) O(1)
for( int i=0; i<=x; ++i )
soma+=i; // O(1)
// O() do loop = O(x) == O(1) + x*O(1) + x*O(1) + x*O(1)
return soma; // O(1)
}
// O() da função = O(x) == O(1) + O(1) + O(x) + O(1)
So this function has O(N) time complexity. Note that this function performs its calculation with a fixed amount of local variables only, so it is O(1) in the space used (i.e., it does not need more memory depending on the input).
The first case is a recursive function, and complexity analysis becomes recursive as well. There’s a solid theory for this, but I’ll stick to one simplistic explanation.
Note that all operations in the body of the function, except the recursive call itself, are O(1). Recursive calls will occur until the termination condition is reached. Note that for an input x = N, occurred N calls. Since in each call, apart from the recursive call, O(1) operations are performed, then the time complexity of this function is also O(N).
The complexity in space of this function differs from case 2. Because it is a recursive function whose result needs to be aggregated as a sum at the end, it is not a function Tail-recursive, and therefore it is not possible for the compiler to optimize its function using this technique.
Given that Tail-recursion it is not possible, at each recursive call it is necessary that if Pops into the call stack a fixed number of data (function arguments, return address, etc.). That is, to N calls, occurred Ndata stacks of a given size, so the function is O(N) in the space it also uses.
Answering the second question: There is another method?
You have two solutions to the problem, one is O(N) in time and O(N) in space, one is O(N) in time and O(1) in space.
An alternative would be to look for a solution whose complexity does not depend on the input value, is that it is possible a solution O(1) in time and O(1) in space?
Note that:
From this formula (a basic deduction of the sum of the elements of an arithmetic progression), it is possible to obtain the sum value from the input value with complexity O(1), that is, without loops.
Then the most efficient method would be:
int Z(int x) { // O(1)
return (x * (x + 1)) / 2; // O(1)
}
(If you’ve ever wondered in life where you would use PA and PG taught in school, there you go ;-) )
If you wanted to be more efficient still, with C++11 you could declare the function as
constexpr.
constexpr int Z(int x) {
return (x * (x + 1)) / 2;
}
Thus, most compilers that supports C++11 would compute the sum at compile time, incurring no runtime calculations, when the argument passed is a constant. If the argument is not a constant (i.e. a runtime value), the function achieves the same version efficiency inline.
Lots of show! + 1
Fantastic response! :)
5
Improving performance:
In g++ there is a flag -Ofast that makes several modifications during the build phase of your algorithm and, most of the time, it gets much more efficient!
Already reduced executions that lasted 20 minutes to less than 1!
Follow an example:
g++ main.cpp -o App.exe -Ofast
Take the test, calculate the runtime as the other answers suggest and draw your own conclusions!
4
On Windows
#include <stdio.h>
#include <windows.h>
int main() {
int i, j;
int inicio, final, tmili;
inicio = GetTickCount();
/* Substitua o for a seguir pelo trecho de código
cujo tempo de execução deverá ser medido. */
for (j = 0; j < 10; j ++)
for (i = 0; i < 1387634340; i ++);
final = GetTickCount();
tmili = final - inicio;
printf("tempo decorrido: %d\n", tmili);
return 0;
}}
On Linux
#include <stdio.h>
#include <sys/time.h>
int main() {
int i, j;
struct timeval inicio, final;
int tmili;
gettimeofday(&inicio, NULL);
/* Substitua o for a seguir pelo trecho de código
cujo tempo de execução deverá ser medido. */
for (j = 0; j < 10; j ++)
for (i = 0; i < 1387634340; i ++);
gettimeofday(&final, NULL);
tmili = (int) (1000 * (final.tv_sec - inicio.tv_sec) + (final.tv_usec - inicio.tv_usec) / 1000);
printf("tempo decorrido: %d\n", tmili);
return 0;
}
4
How to calculate efficiency I don’t know but I can test it:
#include <stdio.h>
#include <time.h>
#include <cstdint>
#ifdef WIN32
#include <Windows.h>
#else
#include <sys/time.h>
#include <ctime>
#endif
/* Returns the amount of milliseconds elapsed since the UNIX epoch. Works on both
* windows and linux. */
uint64_t get_time()
{
#ifdef _WIN32
/* Windows */
FILETIME ft;
LARGE_INTEGER li;
/* Get the amount of 100 nano seconds intervals elapsed since January 1, 1601 (UTC) and copy it
* to a LARGE_INTEGER structure. */
GetSystemTimeAsFileTime(&ft);
li.LowPart = ft.dwLowDateTime;
li.HighPart = ft.dwHighDateTime;
uint64_t ret = li.QuadPart;
ret -= 116444736000000000LL; /* Convert from file time to UNIX epoch time. */
ret /= 10000; /* From 100 nano seconds (10^-7) to 1 millisecond (10^-3) intervals */
return ret;
#else
/* Linux */
struct timeval tv;
gettimeofday(&tv, NULL);
uint64_t ret = tv.tv_usec;
/* Convert from micro seconds (10^-6) to milliseconds (10^-3) */
ret /= 1000;
/* Adds the seconds (10^0) after converting them to milliseconds (10^-3) */
ret += (tv.tv_sec * 1000);
return ret;
#endif
}
int X(int x){
if(x<=0)
return 0;
return(x + X(x-1));
}
int Y(int x){
int soma=0;
for(int i=0;i<=x;++i)
soma+=i;
return soma;
}
int main(void) {
uint64_t startTime, endTime, timeElapsed;
startTime = get_time();
X(300000);
endTime = get_time();
timeElapsed = endTime - startTime;
printf("Tempo decorrido: %d\n", timeElapsed);
startTime = get_time();
Y(300000);
endTime = get_time();
timeElapsed = endTime - startTime;
printf("Tempo decorrido: %d\n", timeElapsed);
return 0;
}
I put in the Github for future reference.
I did a test and the second was clearly much more efficient, at least 7 times faster. I could not post on any site online that allowed you to execute correctly. Where you executed it you cannot share.
The measuring function has been removed from this response in the OS.
"[...] the second was clearly much more efficient [...]" - and the theoretical explanation of why this is very well given in the @pepper_chico reply. :)
Browser other questions tagged c++ loop performance recursion computer-theory
You are not signed in. Login or sign up in order to post.
The second is nicer.
– Victor Martins
Explain better what you mean by "complexity equations"? You want to know which is the most efficient way ?
– lsalamon