Witam
Mam problem ze zbadaniem poprawności i złożoności algorytmu sprawdzającego czy dana liczba jest liczbą automorficzną. Prosiłbym o pomoc kogoś z forumowiczów w tym temacie :) Treść w załączniku bądź na imgurze.
Witam
Mam problem ze zbadaniem poprawności i złożoności algorytmu sprawdzającego czy dana liczba jest liczbą automorficzną. Prosiłbym o pomoc kogoś z forumowiczów w tym temacie :) Treść w załączniku bądź na imgurze.
Jaki problem?
No w tym, że niezbyt ogarniam to. Ze złożonością pamięciowa sobie poradzę, natomiast czasowa to już gorzej. Prosiłbym jakby, ktoś dał radę ją zrobić i tą nieszczęsną poprawność za pomocą niezmienników. Co do symulacji działania to daję radę :P
Masz tylko jedną pętle, w której liczbę na każdym kroku dzielisz przez 10 dopóki nie nie wyjdzie zero, więc - O(log(n))
Mógłbyś to rozpisać? :D
Ale co tu właściwie rozpisywać?
Kod jest w .jpg więc nie dopiszę się do każdej linii oddzielnie, ale cała funkcja poza pętlą ma złożoność stałą ( O(1) ), a pętla:
while (p > 0) { p /= 10; } // albo for (int i = 0; p > 0; i++) jak u ciebie
Wykona się maksymalnie (nitpick: dla p > 0) = O(log (n)) razy (bo każda iteracja w O(1)), więc cała funkcja ma złożoność O(log(n)).
Może znacznie ciekawszym (od rozpisania) jest fakt że funkcja napisana niepoprawnie i nie spełnia założenia.
@_13th_Dragon dałbyś radę to rozpisać jakoś? Chodzi tu o poprawność semantyczną z wykorzystaniem niezmienników. Fakt program jest specjalnie źle napisany i np dla n=24 pokazuje, że liczba jest automorficzna, co jest nieprawdą, jednak to jest zamierzony cel najwyraźniej.
Rozpisać co?
niepoprawność czy O(log(n))?
W sumie jeśli nie sprawi Ci to problemu to obie te rzeczy :D
Złożoność opisał już @msm, powiedz tylko którego słowa nie rozumiesz.
Niepoprawność:
nPomocnicze==0
(owszem przy ujemnych też ale liczby ujemne nie rozpatrujemy).nPomocnicze==0
ogon
zawsze wynosi 0 ponieważ (n/1)*1
zawsze wynosi n
, zaś n-n
zawsze wynosi 0n
jest równe 0