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

Złożoność obliczeniowa

VPS Starter Arubacloud
0 głosów
143 wizyt
pytanie zadane 22 marca 2023 w Algorytmy przez KariPL2 Nowicjusz (120 p.)

Mam takie pytanie odnośnie złożoności obliczeniowej dla programu. Dokładnie chodzi mi o przypadek kiedy mam np. tablice dwuwymiarową 5x5 więc ma ona 25 elementów, jeśli dobrze rozumiem n=25 i w przypadku przejścia po całej tablicy dwoma forami np:

for(int i=0;i<5;i++){

for(int j=0;j<5;j++){

}

}

czy ta złożoność jest równa O(n), ponieważ myślałem nad przykladem, w którym miałbym doczynienia z tablica jednowymiarowa o dlugości 25 i użyłbym do przejścia przez jej elementy jednego fora:

for(int i=0;i<25;i++)

i w tym przypadku wiem ze ta złożoność jest równa O(n)

Dlatego tutaj pojawia się moje pytanie czy to ,że używam dwóch pętli tworzy złożoność mojego algorytmu jest równy O(n^2) ,a może O(n*m) mimo tego, że wykonuje tyle samo kroków jak dal tablicy jednowymiarowej. Jeśli tak bardzo prosiłbym o wyjaśnienie .

Z góry dziękuje

1 odpowiedź

+2 głosów
odpowiedź 22 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Wydaje mi się, że zależy co to jest to N. Możesz powiedzić, że złożonność to O(N*M), gdzie np. N to wysokość tablicy, a M szerokość tablicy, a jeśli N = M, to O(N^2), ale myślę, że teorytycznie możesz powiedzieć, że O(N), gdzie N to liczba pól w tablicy dwuwymiarowej. Trochę zadań algorytmicznych zrobiłem, nigdy nie spotkałem się, żeby ktoś pisał w przypadku tablicy dwuwymiarowej O(N), gdzie N to liczba pól w tablicy dwuwymiarowej. Raczej mówi się O(N*M), lub O(N^2), ale wszystko zależy od przypadku / treści zadania itp.

Jest taka książka "Zaprzyjaźnij się z algorytmami" Jacek Tomasiewicz, gdzie na jego stronie masz darmowe kilka rozdziałów, w tym chyba pierwszy o złożonności: https://www.jacektomasiewicz.pl/_files/ugd/355fe1_b007e66714634c31b439d0b3b86c3720.pdf

lub tu: https://www.jacektomasiewicz.pl/ksiazka

Jak zaczynasz z zadankami, to polecam to forum, szkopuł(archiwalne zadanka np. OIJ, OIG itp.), wspomnianą książkę i OKI.
1
komentarz 22 marca 2023 przez KariPL2 Nowicjusz (120 p.)
super , wielkie dzięki za poradę

Podobne pytania

0 głosów
1 odpowiedź 522 wizyt
pytanie zadane 1 listopada 2020 w Algorytmy przez niezalogowany
0 głosów
2 odpowiedzi 367 wizyt
pytanie zadane 5 grudnia 2019 w Algorytmy przez progNewbie Obywatel (1,130 p.)
0 głosów
0 odpowiedzi 210 wizyt

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

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

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 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!

...