Moda (dominanta) to element ciągu występujący w nim najczęściej. Jeżeli elementy w ciągu nie powtarzają się, to ciąg nie ma mody.
Można spotkać inną definicję, wg której w każdym przypadku istnieje moda, choć może nie być wyznaczona jednoznacznie, kilka elementów można przyjąć jako modę. Przykładowo dla ciągu różnych elementów każdy z nich może być modą.
SPECYFIKACJA Problem: Wyszukiwanie mody w rosnącym ciągu liczb. DANE WEJŚCIOWE Rosnący ciąg n liczb umieszczonych w tablicy L. DANE WYJŚCIOWE Pozycja (indeks) mody w ciągu L. Jeżeli w tablicy nie ma mody, to należy to zasygnalizować.
Rozważymy algorytm wyszukiwania mody na liście uporządkowanej rosnąco lub malejąco (równe elementy są obok siebie). Funkcja zwraca indeks elementu lub None, jeżeli ciąg nie ma mody. Złożoność czasowa algorytmu jest liniowa O(n).
def moda(L, left, right):
"""Wyszukiwanie mody w ciągu rosnącym lub malejącym."""
if left+1 > right:
return None
i1 = None # najlepszy kandydat (indeks)
number1 = 0 # jego liczebność
i2 = left # bieżący element (indeks)
number2 = 1 # jego liczebność
while i2 < right:
i2 += 1
if L[i2] == L[i2-1]: # jeżeli się powtórzył
number2 += 1
# na bieżąco uaktualniamy najlepszego kandydata
if number2 > number1: # jest lepszy kandydat
number1 = number2
i1 = i2
else: # nowy bieżący element
number2 = 1
return i1
Metoda bezpośrednia (naiwna) wyszukiwania mody polega na przeglądaniu kolejnych elementów zbioru i tworzenia dla nich licznika wystąpień. Złożoność jest rzędu O(n^2).
Inna metoda polega na posortowaniu zbioru wybranym algorytmem zaawansowanym o złożoności O(n log n), a następnie wyszukaniu mody w tym zbiorze uporządkowanym ze złożonością O(n).
Wreszcie można stworzyć licznik wystąpień za pomocą słownika (tablicy hashowalnej), co daje złożoność O(n).