Dowód złożoności obliczeniowej
-
- Użytkownik
- Posty: 1
- Rejestracja: 18 lis 2008, o 23:26
- Płeć: Mężczyzna
- Lokalizacja: Dolnoslaskie
Dowód złożoności obliczeniowej
Jak formalnie przedstawić dowód, że dla algorytmów \(\displaystyle{ f \left(x \right)}\) i \(\displaystyle{ g \left(x \right)}\) o złożoności obliczeniowej \(\displaystyle{ O \left(n ^{k} \right)}\) \(\displaystyle{ f \left(x\right) \cdot g \left(x \right) => O ft( n^{2 k} \right)}\) ?
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
Dowód złożoności obliczeniowej
\(\displaystyle{ f(n)=O(n^k)}\) więc istnieje pewna stala \(\displaystyle{ M}\) spelniajaca dla dostatecznie duzych wartosci n: \(\displaystyle{ |f(n)| n^k}\) więc:
\(\displaystyle{ |f(n) g(n)| < M_1 n^k M_2 n^k n^{2k}}\)
czyli
\(\displaystyle{ f(x) g(x) = O(n^{2k})}\)
\(\displaystyle{ |f(n) g(n)| < M_1 n^k M_2 n^k n^{2k}}\)
czyli
\(\displaystyle{ f(x) g(x) = O(n^{2k})}\)