Algoritmus – Matematika – Fórum – Programujte.com

Uff, tak s tímhle nehnu. Nemáte nějaký tip?
Vymyslete algoritmus, který načte řádkově zadanou permutaci n prvků a určí její řád. Odhadněte jeho časovou
složitost.

tak napada me hodne trivialni reseni (nejsem si vubec jist zdali funguje, o permutacich vim minimum), ktere by porovnalo mnozinu a jeji permutaci, cimz by zjistilo jakym zpusobem byly jednotlive prvky permutovany. pote by zkouselo pomoci tohoto pravidla permutovat permutaci puvodni mnoziny a porovnavat ji s puvodni mnozinou, dokud by nedosahlo identity... a pocet takovychto provedenych porovnani by odpovidal radu one permutace. slozitost by byla O(n*k), kde n by zabralo porovnavani dvou mnozin a k pocet celkovych porovnani vsech mnozin... ale fakt nevim, mozna si termin rad permutace spatne interpretuji... tohle je spis na nejaky matfyzacky forum)
dodatek: trosku sem se netrefil s tim odhadem sloztiosti: je treba zapocitat i proces vypocitatni toho pravidla, coz by pravdepodobne probihalo porovnanim kazdeho prvku s nasledujicim, coz by trvalo n*n, tedy vysledne O(n*(k+n)). predpokladam ze permutace je jednoznacna, tedy ze vsechy prvky jsou navzajem ruzne.