Liczenie złożoności obliczeniowej czy dobrze rozpisałem pętle ?

0

Witam, pytanie czy dobrze napisałem/"rozpisałem" liczbę operacji w pętli:
n(1 + 1 + 1 + 1 + 2 + 2) + 1

while(i < n ) tutaj są dwie operację tak ? Te dwie operację będą wykonywane za każdym razem, więc dlatego należy je uwzględnić w nawiasie, jeśli dobrze myślę (1+1 +.........) i na końcu + 1, bo algorytm musi sprawdzić warunek czy się zakończył czy może jednak ten nawias już to uwzględnia. Wiem, że jak się pomylę w liczeniu liczby n to wynik i tak dobry, ale chcę wiedzieć jak to ma być poprawnie zapisane.

 
/* zad.1 Obliczanie średniej arytmetycznej ciągu
   liczb całkowitych o podanej z klawiatury 
   długości. Elementy ciągu również podajemy
   z klawiatury. Ciąg nie jest reprezentowany 
   w tablicy.
 */
int n := 0; //2
int suma := 0; //2
int liczba := 0; //2
int i := 0; //2
real srednia := 0; //2

Print("Podaj ile elementów ma mieć ciąg: "); //1
Read(n); //1
while(i < n)do //1 + 1
    print("Podaj liczbe: ");//1
    Read(liczba); //1
    suma := suma + liczba; //2
    i:=i+1; //2
od
srednia := (real)suma/n; //3
Print("Srednia: " + srednia); //1


1. Liczba charakterstyczna: n.
2. c(n) = 2 + 2 + 2 + 2 + 2 + 1 + 1 + n(1 + 1 + 1 + 1 + 2 + 2) + 1 +3 + 1 = 10 + 2 + 8n + 5 = 17 + 8n

0

Proszę o przeniesienie tego posta do działu edukacja.

1

ale tu nie ma co liczyć rozpisywać.
Widać, że masz pętlę, która wykona się n razy i koniec masz złożoność o(n).
Sumowanie tych jedynek i dwójek nie ma sensu, przykładowo nie jesteś w stanie obliczyć wagi read i print (za tymi funkcjami stoi dużo więcej kodu niż ty sam napisałeś) tak samo nie jesteś w sanie określić wag dla sum liczonych przez ciebie. Za dużo zależy od kompilatora, biblioteki, procesora i miliona innych rzeczy.
To jest właśnie powód, dla którego stosuje się małe 'o' do opisu złożoności algorytmów, bo ono ignoruje te detale, które i tak są niemożliwe do rozsądnego i praktycznego oszacowania.

0

Dzięki Panowie za odpowiedzi. Wiem, że jest dużo różnic itp, ale na razie po prostu kazali nam tak to liczyć.
Pytanie co przyjąć za liczbę charakterystyczną w takim przypadku ? Zakładamy stały rozmiar macierzy 4x3, jeśli dobrze myślę wyjdzie n^2. W załączniku dodałem inny przykład wyliczony, tak jak kazano nam to liczyć. Tylko, że teraz mam problem co będzie tą liczbą charakterystyczną, czy to będzie 12 ?

/*Obliczenie minimalnego elementu macierzy
  o rozmiarze 4x3. Elementy macierzy mają być 
  podawane z klawiatury(wierszami i kolumnami).
 */
  
int min := 0;
int tab[4][3];
int i := 1;
int j := 1;
while(i<=4)do
    while(j<=3)do
        Print("\nPodaj element nr: " +i + ", " + j);
        Read(tab[i][j]);
        j:=j+1;
    od
    i:=i+1;
od

i := 1;
j := 1;
min := tab[1][1];
while(i<=4)do
    while(j<=3)do
        if(tab[i][j]<min)
        min := tab[i][j];
        j:=j+1;
    od
    i:=i+1;
od
Print(min);

 
1

Jak dla mnie skoro masz jasno podane że 4x3 to złożoność jest O(1) i tyle. Rząd złożoności mówi o funkcji według jakiej zmienia się czas wykonania algorytmu w odpowiedzi na zmianę danych wejściowych. Tutaj nie da się rozmiaru danych zmienić, więc rząd jest stały.

0

Pytanie czy tu będzie złożoność pamięciowa O(1) ? Pomijając fakty, że typ int, real zajmują różne rozmiary i szczegóły kompilacji. W załączniku inny przykład jak kazano nam to na razie rozwiązywać. Drugie pytanie, co by się tu musiało zmienić, żeby złożoność pamięciowa tego nie była O(1), tylko inna ?
/*Obliczenie minimalnego elementu macierzy
o rozmiarze 4x3. Elementy macierzy mają być
podawane z klawiatury(wierszami i kolumnami).
*/

int min := 0;
int tab[4][3];
int i := 1;
int j := 1;
while(i<=4)do
    while(j<=3)do
        Print("\nPodaj element nr: " +i + ", " + j);
        Read(tab[i][j]);
        j:=j+1;
    od
    i:=i+1;
od

i := 1;
j := 1;
min := tab[1][1];
while(i<=4)do
    while(j<=3)do
        if(tab[i][j]<min)
        min := tab[i][j];
        j:=j+1;
    od
    i:=i+1;
od
Print(min);

Złożoność obliczeniowa czasowa:
Skoro podane jest,  że macierz ma rozmiar 4x3 to złożoność jest O(1) . 
Rząd złożoności mówi o funkcji według jakiej zmienia się czas wykonania algorytmu w odpowiedzi na zmianę danych wejściowych. Tutaj nie da się rozmiaru danych zmienić, więc rząd jest stały
0

Ty chyba nadal nie rozumiesz. W przykładzie w pdf który podałeś masz ZMIENNĄ liczbę elementów n, więc złożoność obliczeniowa / pamięciowa może być zmienna. W kodzie który podajesz rozmiar problemu jest STAŁY więc złożoność zarówno pamięciowa jak i obliczeniowa są stałe.

1 użytkowników online, w tym zalogowanych: 0, gości: 1