• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Problemy algorytmiczne należące do klasy P.

Object Storage Arubacloud
0 głosów
300 wizyt
pytanie zadane 19 czerwca 2020 w Matematyka, fizyka, logika przez Rrafał98 Nowicjusz (240 p.)
zmienione kategorie 19 czerwca 2020 przez Rrafał98
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.
komentarz 23 czerwca 2020 przez tkz Nałogowiec (42,000 p.)
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.

1 odpowiedź

0 głosów
odpowiedź 18 października 2020 przez J0ker Pasjonat (15,400 p.)
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 .

Podobne pytania

0 głosów
1 odpowiedź 666 wizyt
0 głosów
2 odpowiedzi 312 wizyt
pytanie zadane 20 kwietnia 2020 w Matematyka, fizyka, logika przez Aisekai Nałogowiec (42,190 p.)
0 głosów
0 odpowiedzi 514 wizyt

92,662 zapytań

141,557 odpowiedzi

320,002 komentarzy

62,029 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...