Notacja O/granica ilorazu

[jbeibeadce]

1. Udowodnij dwoma sposobami, że dla dowolnych funkcji f, g i h odwzorowujących N w R+, jeżeli f = O(g) i g = O(h), to f = O(h),
(a) stosując wprost definicję notacji O,
(b) stosując twierdzenie o granicy ilorazu.

2. (a) Napisz algorytm, który wylicza iloczyn dowolnych dwóch liczb całkowitych a i b posługujac się tylko dodawaniem oraz algorytm który wylicza część całkowitą logarytmu przy podstawie 2 z danej liczby n posługując się tylko podstawowymi operacjami arytmetycznymi.
(b) Jaki jest rozmiar zadania, które można rozwiązać Twoim algorytmem w ciagu 1/2h , jeżeli zadanie o rozmiarze 16 algorytm wykonuje w czasie 2s. Pamiętaj, że rozmiar zadania to w tym przypadku liczba bitów potrzebna do zapisania danych.


Jakieś pomysły/rozwiązania? przynajmniej na pkt 1?

[Errichto]

2.
a) Tworzysz jakąś nową zmienną SUMA i \(\displaystyle{ a}\) rady dodajesz do niej \(\displaystyle{ b}\). Musisz do tego uwzględnić przypadek gdy \(\displaystyle{ a<0}\). Jeśli chcesz przyspieszyć program (ten działa liniowo) możesz stworzyć tablicę z wartościami \(\displaystyle{ b}\), \(\displaystyle{ 2b}\), \(\displaystyle{ 4b}\), \(\displaystyle{ 8b}\), ... po czym dodać każdy element do SUMY co najwyżej raz. Jest to równoważne rozważaniu liczby \(\displaystyle{ a}\) w postaci binarnej. Ale to tylko takie opcjonalne zbicie złożoności.
Druga część a) czyli liczenie logarytmu:
Szukasz największej liczby takiej, by dwójka podniesiona do tej potęgi nie przekroczy \(\displaystyle{ n}\). Możesz np. po kolei od \(\displaystyle{ 0}\) w górę sprawdzać, czy to jest wynik (\(\displaystyle{ 2 ^{x}}\) liczysz za pomocą mnożenia).
b) Zapewne chodzi im o to że jeśli \(\displaystyle{ 2^{16}}\) odpowiada dwóm sekundom, to \(\displaystyle{ 2^x}\) odpowiada pół godziny - znaleźć \(\displaystyle{ x}\). Wystarczy policzyć (logarytm o podstawie \(\displaystyle{ 2}\) pewnie się przyda).

[yorgin]

1.

a) Istnieje \(\displaystyle{ N_f}\) oraz \(\displaystyle{ C_f}\) takie, że \(\displaystyle{ f(n)\leq C_f g(n)}\) dla \(\displaystyle{ n\geq N_f}\).

Dodatkowo istnieje \(\displaystyle{ N_g}\) oraz \(\displaystyle{ C_g}\) takie, że \(\displaystyle{ g(n)\leq C_g h(n)}\) dla \(\displaystyle{ n\geq N_g}\).

Zatem dla \(\displaystyle{ n\geq N:=\max\{N_f,N_g\}}\) zachodzi

\(\displaystyle{ f(n)\leq C_f g(n)\leq C_f\cdot (C_g h(n))= C_fC_g h(n)}\)

więc wystarczy jako stałą przyjąć \(\displaystyle{ C:=C_fC_g}\).

b)

Mamy

\(\displaystyle{ \lim\limits_{n\to +\infty}\frac{f(n)}{g(n)}=C_f,\qquad \lim\limits_{n\to +\infty}\frac{g(n)}{h(n)}=C_g}\)

a stąd

\(\displaystyle{ C_fC_g=\lim\limits_{n\to +\infty}\frac{f(n)}{g(n)}\cdot \lim\limits_{n\to +\infty}\frac{g(n)}{h(n)}=\lim\limits_{n\to +\infty}\frac{f(n)}{h(n)}}\)

czyli \(\displaystyle{ f\in \mathcal{O}(h)}\)