złożoność pesymistyczna

0

Witam,
mam taki mały problem i nie wiem jak sobie z nim poradzić, mianowicie pytanie brzmi tak:
Udowodnić, że W(n) = amnm + ... + a1n + ao = O(nm), dla n>0.
Bardzo Proszę o Pomoc i z Góry wszystkim dziękuje

0

Załóżmy ze każdy współczynnik amn jest ograniczony z góry przez odpowiednio dużą stałą K. Następnie skoro
W(n) = amn + ... + a1n + a0 to W(n) <= Kbmn + ... + Kb1n + Kb0 (za każdy współczynnik bierzemy nasze górne ograniczenie, a ciąg bnm jest ciągiem samych 1)
Liczymy sobie sumę tego ciągu jako K * suma ciągu bmn.
Suma bmn = ((1+1)/2)nm = nm
Wynika z tego że W(n) <= K
nm więc O(W(n)) = O(Knm) = O(nm)
(dowód może być bez sensu, tak sobie go teraz wymyśliłem)

0

dokładnie to tak ma wyglądać
Udowodnić, że W(n) = amnm + ... + a1n + ao = O(n^m), dla n>0
gdzie am (m to jest index dolny)
nie zauważyłem że źle mi się wkleiło.

0

Na moje oko to nadal masz to źle przepisane bo kolejność indeksów jest trochę bez sensu. Ale to bez znaczenia. Dowód będzie wyglądał analogicznie do tego który przedstawiłem przed chwilą z tą różnicą że będziesz miał jeszcze stałą m którą skasuje ci O()

0

ajj no masz rację
Udowodnić, że W(n) = amnm + ... + a1n + ao = O(nm), dla n>0
(am gdzie m jest indeksem dolnym)
się zagalopowałem :)
teraz już na pewno dobrze.

0

hmm nie do końca rozumie.

0

Wypisz sobie trochę wyrazów, tak żeby widzieć wszystkie przejscia indeksów. Pogrupuj sobie te wyrazy odpowiednio. Załóż sobie że indeksy aij są ograniczone od góry przez pewną stałą K. Zsumuj tak zgrupowane ciągi. Powyciągaj wszystkie stałe "przed nawias" i potem usuń je wprowadzając notację O()

1 użytkowników online, w tym zalogowanych: 0, gości: 1