Złożoność (objaśnienie)

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
SwiatoweSpiski
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 10 mar 2016, o 14:42
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 7 razy

Złożoność (objaśnienie)

Post autor: SwiatoweSpiski »

Witam. Potrzebuję pomocy, mam zadanie takiej treści:
Wyznaczyć złożoność algorytmu sortowania bąbelkowego:

Kod: Zaznacz cały

 procedure bubble_sort(var A:vector;n:index); 
 var 
 i,j:index; 
 tmp:integer; 
 begin 
 for i:=n-1 downto 1 do 
 for j:=1 to i do 
 if A[j+1] < A[j] then 
 begin 
 tmp:=A[j]; 
 A[j]:=A[j+1]; 
 A[j+1]:=tmp; 
 end; 
 end; 
Chciałbym się dowiedzieć czemu we wewnętrznej pętli zapisujemy \(\displaystyle{ \sum_{j=1}^{i}(4tc)}\). Czemu \(\displaystyle{ 4tc}\), skoro mamy w niej tylko trzy przypisania?
Przy okazji, czy ktoś mógłby mi powiedzieć, w jaki sposób (wiem że to już dawno powinienem umieć) rozpisuje się sumę? Czy wzór wygląda jak się domyślam: \(\displaystyle{ \sum_{k=1}^{n}m=m(n-(k-1))}\)? Jeśli nie, to prosiłbym o naprostowanie.
Ostatnio zmieniony 29 lis 2016, o 13:40 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Niewłaściwe tagowanie.
MatPiotr
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 14 paź 2016, o 20:46
Płeć: Mężczyzna
Lokalizacja: pzn
Podziękował: 1 raz
Pomógł: 1 raz

Złożoność (objaśnienie)

Post autor: MatPiotr »

Nie wiem co to tc. W pętli ostatniej masz 4 operacje. Porównania i 3 przypisania. Sume masz na necie. Po za tym jeżeli masz m no to musisz zdefiniować te m i po prostu dodajesz je od tego co na dole do tego co na górze.
ODPOWIEDZ