Złożoność obliczeniowa algorytmy

Question

Witam, mógłby mi ktoś pomóc określić złożoność obliczeniową algorytmu i wytłumaczyć dlaczego tak?

wynik := n;​

 for i := 1 to n do​

   if (i < wynik and r[i]+r[wynik] <= R)​

    wynik := wynik-1;​

​

​

​

Answer 1

Załóżmy, że to Python ze względu na to, że pytanie umieszczono w takim dziale.

Zazwyczaj to będzie O(n), ponieważ trzonem tego kodu jest iterowanie po n-elementowej tablicy. Innymi słowy złożność jest linowa. W linii 5. odwołujemy się do kontenera po indeksie. I to może być klasyczna pythonowa lista lub słownik. W przypadku obu zazwyczaj wyszukiwanie ma złożność O(1), czyli nie zależy od rozmiaru kontenera, a więc ostatecznie O(n * 1) da nam O(n). Jeśli jednak r jest słownikiem to jest on zaimplementowany jako tablica mieszająca. Wyszukiwanie w niej elementów, gdy znamy indeks, ma zwykle złożność O(1), ale w pesymistycznym przypadku może mieć O(m), gdzie m jest rozmiarem słownika.

Zatem podsumowując, w zależności czym jest r złożność obliczeniowa wynosi:

• O(n*1) = O(n) - zwykle tak będzie gdy r = dict, zawsze tak będdzie gdy r = list
• O(n*m) - pesymistyczny wariant gdy r = dict