Structures de Données et Algorithmes Examen 1

Question 1

T(N) :

Answer 1

(déf: le côut d’un algorithme)
- ça represente le temps d’execution d’un “run” quelconque

Question 2

terme dominant :

Answer 2

une terme est dite dominant si, pour N suffisemment grand, il explique la fonction T(N)

ex:

aN^3 + log(N)

aN^3 est le terme dominant car, à N = 999999999999999, log(N) est négligable.

Question 3

Pourquoi on spécifie “pour N suffisemment grand” explique avec l’exemple N^2 vs 2N

Answer 3

N^2 = 1, 4, 9
2N = 2, 4, 6

si N < 2 2N est supérieur
si N > 2, N^2 est supérieur

so c’est important de spécifier

Question 4

O(N) :

Answer 4

Pire cas d’un algorithme en terme de temps d’execution.
(Maximum execution time for a given algorithm)
(Upper bound)

Question 5

λ(N)

Answer 5

meilleurcas d’un algorithme en terme de temps d’execution.
(Minimum execution time for a given algorithm)
(Lower bound)

Question 6

f(N) = N^2
g(N) = N^3

O() = ?

Answer 6

O(N) = O(max( f(N) , g(N)) )
donc,
O(N) = O(max( N^2 , N^3) )

O(N) = O(N^3) ou O(g(N))

Question 7

f(N) = N^2
g(N) = N

O() = ?

Answer 7

O() = O(max( f(N) , g(N)) )
donc,
O() = O(max( N^2 , N) )

O() = O(N^2) ou O(f(N))

Question 8

boucle O( g(N) )
{
bloc O( f(N) )
}

O() = ?

Answer 8

O( f(N) ⋅ g(N) )

Question 9

boucle O( a(N) )
{
bloc O( b(N) )

bloc O( c(N) ) }

O() = ?

Answer 9

O( a(N) ) ⋅ O( max( b(N) , c(N) ) )

Question 10

ϴ(N) :

Answer 10

si O( f(N) ) et λ( f(N) ) ont la même ordre. On le désigne, ϴ(N).

Question 11

sum of i :

Answer 11

n(n + 1)
_______

   2