Jak obliczyć złożoność mojego algorytmu?

pytanie zadane 18 stycznia 2016 w C i C++ przez Aser Nowicjusz (240 p.)

Witam. Napisałem bardzo prosty algorytm w C++, który wyświetla dwie macierze. Zadanie to było "transponowanie macierzy". Mam wielką prośbę. Algorytm został napisany po tygodniu nauki z youtubem i nie bardzo znam się na C++ jak i samym programowaniu. Jak obliczyć jego złożoność? bardzo, ale to bardzo proszę o wyjaśnienie jak to się liczy i jaką złożoność posiada mój algorytm. Przepraszam z góry, że nie wstawiam kodu, ale jestem w pracy i nie mam w tym momencie do projektu dostępu.
W każdym razie alg jest bardzo prosty i posiada 2x dwie pętle for(int i=0; i<n; i++) for(int j=0; j<n; j++)
jedna para "for" dla jednej macierzy druga dla drugiej. Bardzo proszę o pomoc w zrozumieniu złożoności takiego algorytmu.

5 odpowiedzi

odpowiedź 18 stycznia 2016 przez drek Gaduła (4,980 p.)

http://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych/Wst%C4%99p:_poprawno%C5%9B%C4%87_i_z%C5%82o%C5%BCono%C5%9B%C4%87_algorytmu

Generalnie polecam tę stronę - naprawdę wysokiej jakości wykłady. http://wazniak.mimuw.edu.pl/index.php?title=Strona_g%C5%82%C3%B3wna

Wracając do Twojego kodu:

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

    for(int j=0; j<n; j++) {
        doSomething()
    }
}

To wygląda mi to na złożoność kwadratową O(n^2), bo n razy wykonujesz pętlę zewnętrzną i n wewnętrzną czyli n * n. Ale mogę się mylić, bo miałem to na studiach lata temu i nie jestem świeżo w temacie...

odpowiedź 18 stycznia 2016 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

odpowiedź 18 stycznia 2016 przez Aser Nowicjusz (240 p.)

Ok, bardzo dziękuję za odpowiedzi. Mam nadzieje, że taka odpowiedź przy sprawdzaniu projektu wystarczy - pętla for licząca wiersze i pętla for licząca kolumny = czyli n*n = n^2, jeżeli dobrze zrozumiałem. Pewne rozwiązania rodzą kolejne pytania - co to jest notacja dużego O? i czy jak mój algorytm wyświetla dwie tablice kwadratowe czyli w kodzie są dwie pętle 2xFOR to coś zmienia w złożoności?.
[IMG]http://i65.tinypic.com/24o0g2u.jpg[/IMG]
Tak wygląda jego złożoność czasowa

odpowiedź 18 stycznia 2016 przez Sebastian Fojcik Nałogowiec (43,040 p.)

Można wyznaczyć 2 złożoności algorytmu:

Dokładna - rzadko się używa

Notacja dużego O - jest to taka funkcja, która jest zawsze wyżej niż złożoność dokładna algorytmu.

To co przedstawiłeś na swoim wykresie, to właśnie złożoność dokładna. Taką złożoność opisuje się w dwóch przypadkach danych:

Dane pesymistyczne - najgorszy możliwy układ danych
Dane optymistyczne - najlepszy możliwy układ danych

Czasami algorytmy nie posiadają takiego podziału w zależności od danych.
Wróćmy do tej notacji dużego O. Twój wykres przedstawia zależność czasu od ilości danych. Jest to jakaś tam funkcja. Jakby się uprzeć, to może i wyprowadzisz wzór funkcji maksymalnie zbliżonej do Twojego wykresu, ale informatykom nie jest to potrzebne. Przedstawianie złożoności algorytmów za pomocą skomplikowanych wzorów utrudniłoby porównywanie takich algorytmów. Stworzono więc notację dużego O.

Notacja dużego O jest to taka funkcja fundamentalna, która jest zawsze nad wykresem wykonywania Twojego programu dla danych pesymistycznych. To znaczy, że niezależnie jakie dane wprowadzisz do algorytmu opisanego wzorem: O(n), to Twój algorytm zawsze wykona mniej lub tyle samo operacji ile danych.

Aby lepiej Ci pokazać czym jest notacja dużego O i jak zależna jest od programisty, to taki przykład:

void algorytm()
{
int zmienna = 5;
}

Załóżmy, że utworzenie zmiennej i wpisanie do niej wartości, to jedna operacja. Złożoność tego algorytmu? Dokładna, to oczywiście 1. Zawsze będzie jedna operacja. A notacja dużego O, to taka funkcja, która zawsze będzie równo lub nad. W takim razie dla tego algorytmu poprawne są notacje: O(1), O(n), O(log), O(n^2), O(2^n). Z czego tej pierwszy jest najbardziej trafny, ale zgodnie z definicją notacji dużego O, wszystkie są poprawne.

Teraz posłużę się Twoim obrazkiem z moją drobna edycją w paitcie :-D

Jak widać funkcja O(n^2) jest zawsze nad Twoją złożonością czasową. Zatem za pomocą O(n^2) możesz opisać złożoność czasową swojego algorytmu.
Myślę, że już wiesz o co chodzi z tymi "O"

Pozdrawiam :-)

komentarz 18 stycznia 2016 przez Sebastian Fojcik Nałogowiec (43,040 p.)

PS. Również miałem, to dawno, więc jeśli ktoś ma wątpliwości, to niech śmiało zgłasza. Poprawię. Nie ma nic gorszego niż głoszenie herezji...

... no, jest jeszcze instrukcja goto :-D

komentarz 18 stycznia 2016 przez Aser Nowicjusz (240 p.)

Dzięki ;-) sporo to rozjaśniło w kwestii rozumienia dużego O ;-). Mój algorytm ma złożoność O(n^2) fakt, lecz czy to nie jest 2(n^2) z racji tego, że wyświetla dwie tablice tzn, w algorytmie mam dwie pętle^2?

komentarz 18 stycznia 2016 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

Instrukcja goto to dopiero herezja :) Informatyków nie interesuje stała algorytmu czyli czy to jest 2(n) czy 10000(n) tylko złożoność chodzi o te n

odpowiedź 19 stycznia 2016 przez Aser Nowicjusz (240 p.)

Mam jeszcze jedno malutkie pytanie. Powiedzmy, że

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

for(int j=0; j<n; j++)

tablica[i][j]=rand()%10

W takim przypadku rozumiem, że "i" jest licznikiem iteracji zewnętrznej odpowiadającej za wiersze, a "j" licznikiem iteracji wewnętrznej odpowiadającej za kolumny i to On "fizycznie" przypisuje w podanym (mocno ogólnie) przykładzie powyżej liczby pseudolosowe dla wiersza o indeksie 0, przypisuje je "kolumnami" ????? czy dobrze rozumiem?

komentarz 19 stycznia 2016 przez drek Gaduła (4,980 p.)

Oczywiście, że "fizycznie" przypisuje. W C obliczenia nigdy nie są odkładane "na później" i zawsze od góry do dołu. Jeśli masz kod:

int i = 0;
int j = i;

To masz gwarancję, że po wykonaniu tego kodu, pod "i" masz wartość 0, i pod "j" też masz wartość 0.

A to czy zdefiniujesz "i" jako kolumny a "j" jako wiersza (tab[i][j] czy tab[j][i]), czy odwrotnie, jest kompletnie bez znaczenia[*1]. Ważne jest tylko abyś Ty wiedział o co chodzi oraz używał tych indeksów konsekwentnie w całym programie.

[*1] ok, czasami nie jest bez znaczenia z punktu widzenia wydajności, ale nie będę wchodził w szczegóły

komentarz 19 stycznia 2016 przez Aser Nowicjusz (240 p.)

Ok, rozumiem. Czyli teoretycznie przy nadawaniu wartości w macierzy możemy nawet pominąć pierwszy nawias w tablicy kwadratowej...mam na myśli tablica[ ][3] przypisze wartości i tak bo pierwszy nawias służy za przestawienie na kolejny wiersz.

komentarz 19 stycznia 2016 przez drek Gaduła (4,980 p.)
edycja 19 stycznia 2016 przez drek

Szczerze? Teoretycznie pewnie by się dało skopiować cały fragment pamięci z jednej tablicy do drugiej. Tyle tylko, że moim zdaniem złożoność algorytmiczna pozostanie taka sama, bo na najniższym poziomie i tak masz kopiowanie jednej komórki pamięci do drugiej (elementu tablicy pierwszej do drugiej), i tak dla wszystkich. Jeśli mówimy tutaj o analizie algorytmów, to taki "trik" z wkopiowaniem naraz całego wiersza uważam za nieczysty i ja bym takiego "triku" nie uznał. AFAIK. Kopiowanie bloku pamięci nie ma kosztu stałego, ale ma liniowe (zależy od długości tego bloku), więc nawet gdyby istniała taka składnia, która pozawalałaby kopiować jeden wiersz tablicy do drugiej, to i tak koszt tego byłby N (N - długość tablicy), więc z punktu widzenia analizy algorytmu jest dokładnie to samo jak dwie pętle zagnieżdżone

Jeśli chodzi o praktyczne zastosowanie to możliwe, że są jakieś super szybkie sposoby na kopiowanie fragmentów pamięci, które pozwalają zaoszczędzić cenne mikro (a może nawet mili!) sekundy.