Złożoność oblcizeniowa, niezmiennik pętli

[kamil_lk]

Witam.
Mam do rozwiązania 5 zadań.
1. \(\displaystyle{ P(x)=a_{n}x^{x}+a_{n-1}x^{x-1}+...+a_{1}x+a_{0}}\)
- podać złożoność obliczeniową algorytmu

2.

Kod: Zaznacz cały

begin
forj=n-1 step -1 until 1 do
if A[i+1]<A[i] then
A[i]<-->A[i+1]
end 

- podać pesymistyczną złożoność obliczeniową tego algorytmu

3.

Kod: Zaznacz cały

funktion SILNIA(n)
begin 
if n=0 then
SILNIA := 1
else SILNIA := n*SILNIA(n-1)
end

- podać złożoność obliczeniową algorytmu

4.

Kod: Zaznacz cały

Dane: n
Wynik: liczby k, m takie że m jest nieparzysta oraz m*2^k=n
begin
m:=n
k:=0
while "m jest parzysta" do
begin 
m:=m/2
k:=k+1
end
end

- dowiedź poprawność algorytmów za pomcą niezmienników pętli

5. Napisać algorytm obliczania stopnia dowolnego wierzchołka grafu.

zad.1
\(\displaystyle{ O(2n)}\)
zad.2
\(\displaystyle{ O( n^{2} )}\)
zad.3
\(\displaystyle{ O(n)}\)

Proszę o pomoc z zadaniem 4 i 5 oraz powiedzieć czy zadania 1-3 mają dobre wyniki.

[Crizz]

Jak dla mnie, to zadanie pierwsze jest bez sensu. Wzór to jeszcze nie algorytm, ważne, jak się z niego skorzysta. Pozostałe zadania OK (tak przy okazji: \(\displaystyle{ O(2n)}\) to to samo, co \(\displaystyle{ O(n)}\)).

Niezmiennik pętli do zadania 4. to oczywiście prawdziwość wyrażenia \(\displaystyle{ m\cdot 2^k=n}\). Zauważ, że na samym początku \(\displaystyle{ m=n,k=0}\), czyli \(\displaystyle{ L=n \cdot 2^0=n=P}\). Pokaż, że po każdej pętli ten niezmiennik jest zachowany i że po ostatnim obiegu pętli ma własność wymaganą w zadaniu.

Rozumiem, że to ostatnie zadanie ma być oparte na BFS?

[kamil_lk]

zad.4
\(\displaystyle{ n}\) - nieparzyste
\(\displaystyle{ k=0; m=n}\)
\(\displaystyle{ (m \cdot 2^k=n)}\)<- TRUE
\(\displaystyle{ (m \cdot 2^0=n)}\)<- FALSE
\(\displaystyle{ m \cdot 2^0=n}\)
\(\displaystyle{ m \cdot 1=n}\)
\(\displaystyle{ (m \cdot 2^k=n)}\) <-TRUE

Dla n nieparzystego
Każdą liczbę parzystą można zapisać jako iloczyn 2 oraz liczby 2 razy mniejszej.
Dopóki liczba będzie parzysta zwiększać się będzie potęga naszej 2-ki. Gdy liczba n będzie już nieparzysta to \(\displaystyle{ m \ mod \ 2=0}\) będzie fałszywe, a \(\displaystyle{ m \cdot 2^k=n}\) pozostanie prawdziwe.

To jest przykładowe rozwiązanie mojego kolegi. Da się prościej dla n-nieparzystego?

[Crizz]

Jeszcze prościej?

Wiemy, że przed pierwszym obiegiem pętli wzór jest prawidziwy.

Jeśli wzór jest prawdziwy przed n-tym obiegiem pętli, to przez n+1-szym:
albo \(\displaystyle{ m}\) będzie parzyste, więc pętla się wykona i dostaniemy \(\displaystyle{ m^{\prime}=\frac{m}{2},k^{\prime}=k+1}\). Założyliśmy, że wzór był wcześniej prawdziwy, czyli \(\displaystyle{ m \cdot 2^{k}=n}\). Teraz mamy \(\displaystyle{ m^\prime \cdot 2^{k^\prime}=\frac{m}{2} \cdot 2^{k+1}=m \cdot 2^{k}=n}\), zatem wzór pozostaje prawdziwy.
albo \(\displaystyle{ m}\) będzie nieparzyste, czyli pętla się już nie wykona, wzór jest prawdziwy oraz \(\displaystyle{ m,k}\) spełniają nałożone asercje końcowe.

Generalnie to to samo, co napisałeś w swoim poście, tylko innymi słowami.