Złożoność obliczeniowa - permutacje

Odpowiedz Nowy wątek
2011-05-30 22:39
Trippy
0

Witam,
Mam pytanie: jaką złożoność obliczeniową ma algorytm wyszukujący wszystkie permutacje zbioru np. zbioru liczb? albo ogólnie jaką złożoność ma algorytm brute force?
Tutaj przykład takiego algorytmu:
http://code.google.com/p/goog[...]229d89a54096faaa826671d5d56fc

Nie wiem za bardzo jak to ugryźć, jakby ktoś mógł pomóc to byłbym wdzięczny.

Pozostało 580 znaków

2011-05-30 22:50
0

Może rozpisz algorytm w prostszej formie (np pseudo kodzie), aby dowiedzieć się o jaką permutacje chodzi trzeba analizować kiepsko napisany kod w Javie. Musisz ułatwić zadanie tym kto potencjalnie zechce ci pomóc.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2011-05-30 23:14
Trippy
0

Ok, ogólnie to nie musi być złożoność obliczeniowa tego kodu powyżej.
Chodzi mi o permutacje, gdzie mam daną tablice n-elementową i chce uzyskać jej
wszystkie permutacje (bez powtórzeń). Przy założeniu, że na wyjściu chce uzyskać
permutację, która będzie tablicą n-elementową. Na chłopski rozum wydaje mi się, że w przypadku
optymistycznym np. dla danych wejściowych [1, 1] złożoność obliczeniowa będzie wynosiła 1, a w przypadku pesymistycznym
np. dla danych wejściowych [1, 2, 3] ta złożoność będzie wynosić n! lub 2^n (tu mam dylemat, która odpowiedź jest właściwa).

Pozostało 580 znaków

2011-05-30 23:22
eryk
0

Liczba permutacji ciągu n elementowego to n!, zatem ten algorytm ma złożoność n!

Pozostało 580 znaków

2011-05-31 11:56
0

Chodzi mi o permutacje, gdzie mam daną tablice n-elementową i chce uzyskać jej
wszystkie permutacje (bez powtórzeń). Przy założeniu, że na wyjściu chce uzyskać
permutację, która będzie tablicą n-elementową.

Dla danych [1,1] złożoność obliczeniowa wynosi 0 ponieważ nie istnieje żadna permutacja dwuelementowa bez powtórzeń.
dla danych [1,2,3] złożoność obliczeniowa wynosi n! jak napisał autor postu wyżej.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2011-05-31 12:14
bo
0

Ja bym chętnie zobaczył dowód. Wypisanie tych permutacji wymaga n! operacji, więc złożoność jest >=n!, ale wpierw te permutacje trzeba jakoś utworzyć.

Pozostało 580 znaków

2011-05-31 16:16
0

Nie wiem jak ten algorytm tu wklejony ale np. ten:

def permutations[T](set: Set[T]): Iterable[List[T]] = {
  if (set.isEmpty) 
     List(Nil)
  else 
     for (elem <- set; rest <- permutations(set - elem)) yield elem :: rest
}

ma złożoność n! i do tego jest zawstydzająco krótki w porównaniu z tym koszmarkiem Javowym wklejonym przez autora. :D

edytowany 2x, ostatnio: Krolik, 2011-05-31 16:17

Pozostało 580 znaków

2011-05-31 17:30
bo
0

Próbowałem obejrzeć ten chwalony kod, FF odpowiedział błędem 500, Opera pokazała kod. Nie chciało mi się go analizować, ale podany na początku przykład wskazuje,że mimo nazwy permutacja kod nie całkiem generuje permutacje, on generuje wszystkie k-elementowe, różnowartościowe podciągi ciągu n-elementowego. Liczebność tego tworu wynosi C(n,k)*k!=n!/(n-k)!, C(n,k) to symbol Newtona. Jeżeli k=n, to dostajemy permutacje zbioru n-elementowego.

Pozostało 580 znaków

2011-05-31 18:44
0
bo napisał(a)

Ja bym chętnie zobaczył dowód. Wypisanie tych permutacji wymaga n! operacji, więc złożoność jest >=n!, ale wpierw te permutacje trzeba jakoś utworzyć.

Zazwyczaj w analizie algorytmu nie liczymy operacji wejścia-wyjścia.

edytowany 2x, ostatnio: JumpSmerf, 2011-05-31 18:47

Pozostało 580 znaków

2011-05-31 19:10
0

@JumpSmerf ech ale żeby móc wypisać te wszystkie permutacje to musisz je też mieć wcześniej "policzone", to znaczy że i tak złożoność musi być przynajmniej n! bo jakoś te permutacje wyznaczyliśmy. Nawet jeśli pominiemy sam fakt ich późniejszego wypisania na wyjście.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2011-05-31 21:00
0

Złożoność dla zwracania wszystkich permutacji jest co najmniej n!, ale można nieco to obejść dostarczając leniwą implementację - tzn. taką, która zwraca iterator po wszystkich permutacjach. Samo zwrócenie iteratora da się wtedy zrobić w czasie stałym, a ostateczna złożoność będzie zależeć od tego ile permutacji użytkownik zechce przeczytać. Wliczenie wypisywania permutacji zwiększa złożoność z O(n!) do O(n * n!).

edytowany 1x, ostatnio: Krolik, 2011-05-31 21:03

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0