Programik :)

[azedor]

Poniższe zdaaie pochodzi z ksiazki "Algorytmy i strkutury danych" H.Cormena i innych autorów.

 

Mam dany zbiór liczb całkowitych S, oraz liczbę całkowitą X. Program ma sprawdzić czy istnieją w tym zbiorze dwie liczby ktorych suma wynosi X.

Oczywiscie do tego momentu to zdania jest trywialne :), ale chodzi o to żęby ten program (funkcja) działałą w czasie O(n*lg(n)), gdzie n to ilość danych wejsciowych, lg to logarytm o podstawie 2, O - to złożoność obliczeniowa programu (zazwyczaj uzywa się symbolu theta).

Wiem jak rozwiązać to zadanie w przypadku gdy zbiór jest posorotwany, wtedy jestem w stanie napisać funkcje o takiej złożonośći, ale w zdaniu nic nie jest powiedziane, że zbiór jest posorotwany, więc póki co to nie wiem jak to zrobić.

 

Możliwe, że to zadanie będzie opieralo się na rekurencji, z dzieleniem zbioru na połowe, wtedy mielibyśmy dokładnie lg(n) poziomów rekursji, ale może ktoś ma inny pomysł jak to zrobić.

Edytowane 26 Czerwca 2006 przez azedor

[Ragnor]

To co za problem posortuj sobie ten zbiór. Zajmie Ci to O(nlgn) potem użyj swojego algorytmu na posortowanym zbiorze też zajmie to O(nlgn) co łącznie da: O(nlgn) i po sprawie :-P .

[azedor]

To co za problem posortuj sobie ten zbiór. Zajmie Ci to O(nlgn) potem użyj swojego algorytmu na posortowanym zbiorze też zajmie to O(nlgn) co łącznie da: O(nlgn) i po sprawie :-P .

złozoność O(2nlgn) to to samo co O(nlgn) ? :) jeśli tak to to można zrobić tak jak powidziałeś :)

[Ragnor]

złozoność O(2nlgn) to to samo co O(nlgn) ? :) jeśli tak to to można zrobić tak jak powidziałeś :)

To to samo :D, nawet O(100*nlgn) to też O(nlgn), wkońcu 100 to tylko stała. Warto najpierw poznać te miary złożoności (jeszcze omega i teta są często wykorzystywane), bo to się często przydaje.