Algorytmy - złożoność

pytanie zadane 6 lutego 2017 w C i C++ przez kmarcin Użytkownik (590 p.)

Która z odpowiedzi jest poprawna:

1. Problem którego najlepsze rozwiązanie ma złożoność obliczeniową O(n!) należy do klasy problemów:

- łatwych

- NP- zupełnych

- trudnych

- nierozstrzygalnych

2. Problem komiwojażera jest problemem:

- łatwym

- NP- zupełnym

- trudnym

- nierozstrzygalnym

Ja dałbym w obydwu przypadkach odpowiedź trudne, ale chciałbym znać Waszą opinię.

1	komentarz 6 lutego 2017 przez koczurekk Gaduła (3,420 p.) W pierwszym chyba chodzi o trudne, w drugim zależy od definicji problemu i odpowiedź to albo NP–trudny, albo NP–zupełny.

1 odpowiedź

odpowiedź 7 lutego 2017 przez zperkowski Stary wyjadacz (11,150 p.)

Wystarczy otworzyć pierwszą lepszą książkę. W każdej książce, którą widziałem na temat algorytmów jest zestawienie danych złożoności obliczeniowych oraz szacunkowe czasy zakończenia programu dla podanych danych wejściowych. W Google na pewno również się znajdzie. A już na pewno odpowiedź na drugie pytanie. Wikipedia?

[...] chciałbym znać Waszą opinię.

Tu nie chodzi o opinie. Klasyfikacja złożoności problemu to nie czyjaś opinia. Opinie mogą być różne, fakt jest jeden.

1	komentarz 7 lutego 2017 przez kmarcin Użytkownik (590 p.) Być może źle się wyraziłem z tą opinią. Po prostu chcę wiedzieć jak jest. W zasadzie to nic nie pomogłeś a jedynie chyba szukasz spiny.

komentarz 7 lutego 2017 przez zperkowski Stary wyjadacz (11,150 p.)

Spiny to Ty szukasz nie czytając regulaminu

2. Zadając pytanie Pasjonat zobowiązany jest do przestrzegania następujących zasad:

A. przed zadaniem pytania należy sprawdzić przy użyciu wyszukiwarki czy podobne lub identyczne pytanie nie zostało już zadane,

[...]

G. zabronione jest proszenie o gotowe rozwiązanie danego zadania/problemu,

Pierwszy i trzeci wynik z Google. Serio to było trudne?

https://pl.wikipedia.org/wiki/Problem_komiwojażera
http://home.agh.edu.pl/~horzyk/lectures/pi/ahdydpiwykl8.html