Liczba automorficzna - poprawność i złożoność

1

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.

user image

0

Jaki problem?

0

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

0

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))

0

Mógłbyś to rozpisać? :D

1

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 \lfloor \log_{10} p \rfloor + 1 (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)).

0

Może znacznie ciekawszym (od rozpisania) jest fakt że funkcja napisana niepoprawnie i nie spełnia założenia.

0

@_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.

0

Rozpisać co?
niepoprawność czy O(log(n))?

0

W sumie jeśli nie sprawi Ci to problemu to obie te rzeczy :D

0

Złożoność opisał już @msm, powiedz tylko którego słowa nie rozumiesz.
Niepoprawność:

  1. Z pętli for jest tylko jedno wyjście nPomocnicze==0 (owszem przy ujemnych też ale liczby ujemne nie rozpatrujemy).
  2. Math.pow(10,nPomocnicze) zawsze będzie wynosić 1 ponieważ nPomocnicze==0
  3. ogon zawsze wynosi 0 ponieważ (n/1)*1 zawsze wynosi n, zaś n-n zawsze wynosi 0
  4. Funkcja zwróci wartość 1 tylko jeżeli n jest równe 0

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