⌘ '

raccourcis clavier

Complexity analysis

algorithm = takes one-or-more values, produces an outputs

Ex: contains

Given a list of $L$ and value $v$ , return $v \in L.$

Input: $L$ is an array, $v$ is a value Output: true if $v \in L$ , false otherwise

i, r := 0, false
while i neq |L| do
  if L[i] = v then
    r := true
    i := i + 1
  else
    i := i + 1
return r

invariants

Induction hypothesis that holds at beginning of iteration.

Deterministic

Base case: inv holds before the loop
Hypothesis: holds after j-th, j<m repetition of loop
Step: assume inv holds when start m-th loop, proves it holds again at the end of m-th loop

Are we done?

Assuming invariant → does it reach conclusion
Does it end?

Formal argument: prove a bound function

bound function $f$ on the state of the algorithm such that the output of $f$

natural number (0, 1, 2, …)
strictly decreases after each iteration

$f=|L| - i$ starts at $|L|, |L| \geq 0$

correctness.

pre-condition: restriction require on input
post-condition: should the output be
prove the running the program turns pre-condition and post-condition

complexity.

assume V is not in the list Contains(N) = 5 + 7N

given V is in the list

contains is correct, runtime complexity is $\text{ContainsRuntime(|L|)}=|L|$ and memory complexity is $\text{ContainsMemory(|L|)}=1$

runtime.

graph comparison

models are simplification.

shows different growth rates.

Interested in scalability of algorithm For large enough inputs, contains will always be faster than altc because order of growth of $\text{CRuntime} < \text{AltCRuntime}$
Growth

upper bounded (at-most)

$f(n) = \mathcal{O}(g(n)) \iff \space \exists \space n_{0}\ , c>0 \mid 0 \leq f(n) \leq c \cdot g(n) \space \forall \space n \geq n_{0}$

lower bounded (at-least)

$f(n) = \Omega(g(n)) \iff \space \exists \space n_{0}\ , c>0 \mid 0 \leq c \cdot g(n) \leq f(n) \space \forall \space n \geq n_{0}$

equivalent (strictly bounded)

$f(n) = \Theta(g(n)) \iff \space \exists n_{0}, c_{lb}, c_{ub} \mid 0 \leq c_{lb} \cdot g(n) \leq f(n) \leq c_{ub} \cdot g(n) \forall n \geq n_{0}$

algorithm = takes one-or-more values, produces an outputs

Ex: contains

Given a list of $L$ and value $v$ , return $v \in L.$

Input: $L$ is an array, $v$ is a value Output: true if $v \in L$ , false otherwise

i, r := 0, false
while i neq |L| do
  if L[i] = v then
    r := true
    i := i + 1
  else
    i := i + 1
return r

invariants

Induction hypothesis that holds at beginning of iteration.

Deterministic

Base case: inv holds before the loop
Hypothesis: holds after j-th, j<m repetition of loop
Step: assume inv holds when start m-th loop, proves it holds again at the end of m-th loop

Are we done?

Assuming invariant → does it reach conclusion
Does it end?

Formal argument: prove a bound function

bound function $f$ on the state of the algorithm such that the output of $f$

natural number (0, 1, 2, …)
strictly decreases after each iteration

$f=|L| - i$ starts at $|L|, |L| \geq 0$

correctness.

pre-condition: restriction require on input
post-condition: should the output be
prove the running the program turns pre-condition and post-condition

complexity.

assume V is not in the list Contains(N) = 5 + 7N

given V is in the list

contains is correct, runtime complexity is $\text{ContainsRuntime(|L|)}=|L|$ and memory complexity is $\text{ContainsMemory(|L|)}=1$

runtime.

models are simplification.

shows different growth rates.

Interested in scalability of algorithm For large enough inputs, contains will always be faster than altc because order of growth of $\text{CRuntime} < \text{AltCRuntime}$
Growth

upper bounded (at-most)

$f(n) = \mathcal{O}(g(n)) \iff \space \exists \space n_{0}\ , c>0 \mid 0 \leq f(n) \leq c \cdot g(n) \space \forall \space n \geq n_{0}$

lower bounded (at-least)

$f(n) = \Omega(g(n)) \iff \space \exists \space n_{0}\ , c>0 \mid 0 \leq c \cdot g(n) \leq f(n) \space \forall \space n \geq n_{0}$

equivalent (strictly bounded)

$f(n) = \Theta(g(n)) \iff \space \exists n_{0}, c_{lb}, c_{ub} \mid 0 \leq c_{lb} \cdot g(n) \leq f(n) \leq c_{ub} \cdot g(n) \forall n \geq n_{0}$

Complexity analysis

Étiquette

publié à

modifié à

durée

source

invariants

correctness.

complexity.

runtime.

Vous pourriez aimer ce qui suit

Liens retour