Temat 5: Złożoność obliczeniowa (II)

Wstecz; Ostatnia modyfikacja: 13.03.2015

---

• Ćw wstępne: dokończyć zadanie z poprzednich zajęć
• Wyszukiwanie liniowe $\Theta(n)$ vs. wyszukiwanie binarne $\Theta(log(n))$

@timeit
def lin_search(l,x):
  n = len(l)
  for i in range(n):
    if l[i] == x:
      return i
  return -1

@timeit
def bin_search(l, x):
  n = len(l)
  a = 0; b = n

  while (b-a > 1):
    c = (b+a) / 2
    if l[c] == x: return c
    elif l[c] > x: b = c
    elif l[c] < x: a = c
  return -1

l=range(0,1000000,3)
c = bin_search(l, 37)
print(c)

c = lin_search(l, 37)
print(c)

# Running time of bin_search: 1.69277191162e-05
# Running time of lin_search: 0.0184202194214

• Zapoznaj się ze złożonością obliczeniową operacji na kluczowych strukturach danych w Pythonie: link
• Ćw 1: napisz funkcję, która dla danej listy $l=[x_1,...,x_n]$ i liczby całkowitej $r$ zwraca listę indeksów $i$ takich, że (a): $$x_{i-r} < ... < x_{i-1} < x_i > x_{i+1} > ... > x_{i+r}$$. Jaką złożoność obliczeniową ma Twój algorytm? Wariant (b) $$x_i = max(x_{i-r},..., x_{i-1},x_i, x_{i+1},..., x_{i+r})$$
• Ćw 2:Jakie znasz algorytmy sortowania? Jaka jest ich złożoność obliczeniowa?

def bubble_sort(arr):
  def swap(i,j):
    t = arr[i]
    arr[i] = arr[i+1]
    arr[i+1] = t

  n = len(arr)
  for k in range(n-1, 0, -1):
    for i in range(k):
      if arr[i] > arr[i+1]:
        swap(i,i+1)
  return arr

def quick_sort(arr):
    if len(arr)<=1:
        return arr
    pivots = [x for x in arr if x == arr[0]]
    lesser = quick_sort([x for x in arr if x < arr[0]])
    greater = quick_sort([x for x in arr if x > arr[0]])

    return lesser + pivots + greater

def merge_sort(arr):
  def merge(left, right):
      result = []
      i = j = 0
      while i < len(left) and j < len(right):
          if left[i] < right[j]:
              result.append(left[i])
              i += 1
          else:
              result.append(right[j])
              j += 1
      result += left[i:]
      result += right[j:]
      return result

  if len(arr) < 2:
      return arr
  m = len(arr) / 2
  return merge(merge_sort(arr[:m]), merge_sort(arr[m:]))

• Ćw 3 (opcjonalnie): Przanalizuj złożoność czasową różnych algorytmów liczenia n-tego elementu ciągu Fibonacciego. Rekurencyjny: $\Theta\big(\big(\frac{1+\sqrt(5)}{2}\big)^n\big)$ (dlaczego?), $\Theta(n)$, $\Theta(log(n))$.
• Ćw 4 (opcjonalne): Zaimplementuj potęgowanie liczb w czasie logarytmicznym.
• Kod z ćwiczeń