Matematyka.pl

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



Algorytm jeden


Algorytm dwa


Który z nich jest sprawniejszy i dlaczego?

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.

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

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

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.

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.

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.

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