On 08.08.2009, Wojciech Muła wrote:
> "Stachu 'Dozzie' K." <d...@d...im.pwr.wroc.pl.nospam> wrote:
>
>> To może pora się douczyć o złożoności obliczeniowej i o sposobach
>> wyrażania stopnia trudności problemów, panie "u nas w hameryce ja ktoś
>> mi mówi, to ja mu wierzę, a w Polsce to w ogóle brud, smród i ubóstwo"?
>> Bo ilość czasu potrzebną do rozwiązania problemu podaje się właśnie jako
>> zależność ilości operacji od ilości danych wejściowych dla algorytmu
>> optymalnego (albo przynajmniej najlepszego znanego).
>
> Skoro się tak czepiasz[1], to powiedz jaką złożonośc ma algorytm (optymalny,
> względnie najlepszy) rozwiązywania problemu pod tytułem sortowanie? :)

Ogólny problem sortowania wektora, bez podawania dodatkowych ograniczeń
na dane wejściowe, ma złożoność pesymistyczną O(n * lg(n)). Jeśli wiesz
coś zawczasu o danych wejściowych, możesz zejść poniżej tego czasu (na
przykład dla sortowania pojedynczych liczb można osiągnąć O(n), a dla
sortowania wektora nie większego niż X osiągasz O(1)).

A co to ma do rzeczy?

--
Stanislaw Klekot