Złożoność obliczeniowa

Question

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

Answer 1

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.

Comments

super , wielkie dzięki za poradę