Question

Określ złożoność algorytmu: Alicja po drodze do szkoły postanowiła wstąpić do kawiarni. Na miejscu okazało się, że mają promocję – kawa i ciastko w cenie 10 zł. Alicja popatrzyła na spis produktów i doszła do wniosku, że czasem promocja ta się bardzo opłaca, a czasem wychodzi się na tym stratnie. Dopasowała więc szybko wszystkie kawy do wszystkich ciast i wszystkie zestawy, które w sumie przekraczały 10 zł, zapisała na kartce. Z wybranego podzbioru wybrała zestaw, który najbardziej lubi i zamówiła go.

Answer 1

Najpierw dobieramy wszystkie ciastak z wszystkimi kawami czyli N*M, teraz iterujemy po tych wyborach i patrzymy, które są powyżej 10 zł (N*M operacji), i wubieramy jakiś jeden zestaw 2*N*M + 1, czyli złożoność algorytmu to O(N*M)