• 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
281 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ź 640 wizyt
0 głosów
2 odpowiedzi 300 wizyt
pytanie zadane 20 kwietnia 2020 w Matematyka, fizyka, logika przez Aisekai Nałogowiec (42,190 p.)
0 głosów
0 odpowiedzi 501 wizyt

92,558 zapytań

141,407 odpowiedzi

319,569 komentarzy

61,945 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

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

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!

...