Dwa algorytmy, który lepszy.

[Kanodelo]

Dane są algorytmy które mogą policzyć sume \(\displaystyle{ 2+4+...+2N}\).



Algorytm jeden

Kod: Zaznacz cały

(1) Niech S<-0

(2) Dla I od 1 do N wykonaj

(2.1) I<-2&I

(2.2) S<-S+I

(3) Wypisz S

Algorytm dwa

Kod: Zaznacz cały

(1) Niech S<-0

(2) Dla I od 1 do N wykonaj

(2.1) S<-S+I

(3) Niech S<-S*2

(4) Wypisz  S

Który z nich jest sprawniejszy i dlaczego?

[PMichalak]

Pierwszy wykonuje n mnożeń i n dodawań (nie licząc inkrementacji w pętli).
Drugi wykonuje 1 mnożenie i n dodawań, więc drugi będzie szybszy, jednak oba są nieoptymalne.

[Errichto]

Oba są tak samo złe, mają tę samą złożoność.
Lepsze byłoby wyliczenie wyniku ze wzoru na sumę ciągu arytm.

[PMichalak]

Mierzone operacjami bitowymi mnożenie ma większą złożoność niż dodawanie.

[Errichto]

Bezsensowne by było ocenianie programów z takimi szczegółami. Dla większych programów byłoby to niewykonalne.

W obu przypadkach złożoność liniowa, z bardzo małą stałą - i tyle.

[PMichalak]

Jak już mówiłem to zależy od przyjętego kryterium zlożoności, jeśli przyjmiemy, że dodawanie i mnożenie zajmuje stały czas to masz racje, jednak jeśli mierzysz operacje na bitach to dodawanie ma złożoność \(\displaystyle{ \Theta (log n)}\) natomiast najszybsze mnożenie teoretycznie \(\displaystyle{ \Theta (log n \cdot log log n \cdot \log log log n)}\), więc nie są asymptotycznie równoważne.

[Errichto]

Dla prostych algorytmów takie szczegóły są bez znaczenia.
Dla trudniejszych takie wyliczenie jest awykonalne.
Zawsze uczyłem się, że operacjami podstawowymi są np. dodawanie i mnożenie, a np. pierwiastkowanie daje po prostu większą stałą.
Tak też jest w szkolnych podręcznikach i na omówieniach zadań typu OI. Wiki też proponuje taki system.
Nie wiem jak jest na studiach i dalej - może czasem się uznaje operacje bitowe za podstawowe i na ich podstawie określa złożoność. No ale ja się z tym nie spotkałem.

[PMichalak]

Operacjami bitowymi mierzy się zazwyczaj złożoność algorytmów teorioliczbowych.