Problemy algorytmiczne należące do klasy P.

Question

Witam,

Mam takie pytanie: skoro problemy algorytmiczne należące do klasy P można rozwiązać za pomocą algorytmów o złożoności wielomianowej, to czy w grę wchodzi taka złożoność O(n) ? Wiem, że przedstawia się ją jako liniową, ale słyszałem, że jest szczególnym przypadkiem złożoności wielomianowej. Czy ktoś mógłby mi to troszkę bardziej przybliżyć? Z góry dziękuję za odpowiedz.

Comments

Złożoność wielomianowa, to taka, którą da się ograniczyć od góry. Ogólnie jest to O(n^k), za to Ty wspominasz o O(n) jak specjalnym przypadku. Właściwie to spełnia założenia złożoności wielomianowej, bo O(n^k), gdzie k=1 da po prostu O(n), ważne by k było liczbą całkowitą dodatnią. Sama złożoność jest dość rozległym tematem. Więc pewnie jakiś algorytmik wytłumaczy to lepiej i dokładniej.

Answer 1

Jeśli problem ma złożoność wielomianową to istnieje liczba rzeczywista nieujemna, że problem można rozwiązać w czasie O(n^l).

Jeśli nie ma złożoności wielomianowej, to tkie k nie istnieje.

Nie każdy problem z klasy P ma złożoność O(n). Na przykład żaden algorytm mnożenia 2 macierzy nie może zejść poniżej O(n^2). Standardowy algorytm ma złożoność O(n^3). Istnieje wiele algorytmów ze złożonością O(n^k) gdzie k jest między 2 a 3. Aktualnie najlepsze k to chyba około 2,31 .