Temat 4: Złożoność obliczeniowa (I)

Wstecz; Ostatnia modyfikacja: 9.03.2015
  • Ćw 1: co wypisze poniższy program
    • def funkcja1(x, y, *args, **kwargs):
  return "".join([kwargs[a] for a in args])

d={"x1":"a","x2":"b","x3":"c"}
print(funkcja1(*sorted(d.keys()), **d))
  • Ćw 2: zaimplementuj dekorator timeit, do mierzenia czasów wykonania funkcji. Rozwiązanie.
  • Złożoność obliczeniowa: definicje. Niech $f,g\in \mathbb{N}\rightarrow \mathbb{R}_{+}$, wtedy
    • $$f(n) \in \Theta(g(n)) \Leftrightarrow \exists_{c_1,c_2\in \mathbb{R}_{+}}\exists_{n_0\in \mathbb{N}}\forall_{m\geq n_0} \Big(c_1\cdot g(m) \leq f(m) \leq c_2 \cdot g(m)\Big)$$ $$f(n) \in O(g(n)) \Leftrightarrow \exists_{c\in \mathbb{R}_{+}}\exists_{n_0\in \mathbb{N}}\forall_{m\geq n_0} \Big(f(m) \leq c \cdot g(m)\Big)$$ $$f(n) \in \Omega(g(n)) \Leftrightarrow \exists_{c\in \mathbb{R}_{+}}\exists_{n_0\in \mathbb{N}}\forall_{m\geq n_0} \Big(c \cdot g(m) \leq f(m)\Big)$$
  • Ćw 3: Zbadaj zależności pomiędzy funkcjami: $$1,15,n,2\cdot n,n+2,log(n),log(n-2)$$ $$nlog(n),nlog(n)+n, nlog(n)-n, n^2, n^3,log(n!),2^n,3^n,e^n,n!,n^n$$
  • Ćw 4: Zaproponuj algorytm wyznaczania $(\hat{i},\hat{j})$, gdzie:
    • $$(\hat{i},\hat{j})=argmax_{0\leq i \leq j < n} l[j]-l[i]$$ Zaimplementuj rozwiązanie $\Theta(n^2)$ oraz $\Theta(n)$. Porównaj czasy działania.
  • Kod z ćwiczeń.