blob: 116cf842e6e6013b78ac4edefc2aa6b3f4ca0f5e (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
#include<iostream>
#include<cstdlib>
#include<ctime>
void f1 ( int n);
void f3 (int n);
void g2 (int n);
void f1 (int n){
for (int i = 1; i <=n; i ++){
}
}
void f3 (int n ) {
for (int i = 1; i <=n; i ++){
for (int i = 1; i <=n; i ++){
for (int i = 1; i <=n; i ++){
}
}
}
}
void g2 (int n){
if ( n != 1){
g2(n-1);
g2(n-1);
}
}
void g3 (int n){
if ( n != 1){
g3(n-1);
g3(n-1);
g3(n-1);
}
}
int main ( int argc, char ** argv){
if ( argc != 2){
std::cout<<"Syntaxe attendue : ./R1 n"<<std::endl;
return 0;
}
int N = atoi(argv[1]);
std::cout<<"N vaut : "<< N<<std::endl;
time_t timer =time(NULL);
f1(N);
int tmpf1= time(NULL)-timer;
std::cout<<"Temps exec f1 : "<<tmpf1<<std::endl;
timer= time(NULL);
f3(N);
int tmpf3 = time(NULL)-timer;
std::cout<<"Temps exec f3 : "<<tmpf3<<std::endl;
timer = time(NULL);
g2(N);
int tmpg2= time(NULL)-timer;
std::cout<<"Temps exec g2 : "<<tmpg2<<std::endl;
timer = time(NULL);
g3(N);
int tmpg3 = time(NULL)-timer;
std::cout<<"Temps exec g3 : "<<tmpg3<<std::endl;
return 0;
}
/*
Pour n = 1000, f1 mets 0 secondes, contre 2 secondes pour f3;
Vers n= 30 on voit que g2 mets plus de temps que f3
A partir de n = 20, g3 commence a mettre drastiquement plus de temps que g2 ( 4 secondes sur ma machine!)
Concernant les complexités de l'exec successives de fonctions, exemple pour la premiere :
O(n^3) et O ( n + n^3) appartiennent tout deux a teta(n^3) il existe un difference de complexité lineaire, mais elle est negligeable face a n^3
Ce principe s'applique de maniere similaire aux autres questions, a chaque fois la complexité de la premiere fonction est negligeable face a celle de la secone.
*/
//g++ Q1.cpp -o R1
|
