złożoność pesymistyczna

Odpowiedz Nowy wątek
2011-09-28 11:08
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

Pozostało 580 znaków

2011-09-28 12:09
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) <= Knm więc O(W(n)) = O(Knm) = O(n*m)
(dowód może być bez sensu, tak sobie go teraz wymyśliłem)


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2011-09-28 12:10

Pozostało 580 znaków

2011-09-28 12:40
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.

Pozostało 580 znaków

2011-09-28 13:13
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()


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2011-09-29 10:33
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.

Pozostało 580 znaków

2011-10-02 20:34
0

hmm nie do końca rozumie.

Pozostało 580 znaków

2011-10-02 20:37
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()


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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