Matematyka.pl

Witam
MAm takie zadanko z którym do pewnego stopnia (chyba) się uporałem
Spłodziłem do tego taki pseudokod:

Tyle udało mi się wymodzić. Jak zabrać się za policzenie złożoności obliczeniowej ? Generalnie wydaje mi się, że algorytm ma złożoność kwadratową, bo jest pętla w pętki ale pewności nie mam. Podpowie ktoś jak zabrać się do obliczeń ?

A zastanów się czy jest sens zawsze zaczynać druga pętle od zera. Wtedy sprawdzasz niektóre pary wielokrotnie. Spróbuj to poprawić.

Algorytm napisany przez Ciebie ma pesymistyczną złożoność \(\displaystyle{ O(n^{2})}\).
Dlaczego? Koszt 3 linijki jest stały, W przypadku gdy nie istnieje taka para, 3 linia jest wykonywana \(\displaystyle{ n^2}\) (lub jeśli zastosujesz radę kolegi wyżej \(\displaystyle{ \frac{n(n-1)}{2} = O(n^{2})}\) razy,

abc666, a jak inaczej proponujesz ? bo nie kumam ?

czyli jeżeli dobrze rozumuję powyższy wzór wziął się ze wzoru na ciąg arytmetyczny ? i to jest pesymistyczna złożoność . a co ze średnią?

Wzór wziął się albo z sumy szeregu arytmetycznego, albo tego, że po prostu rozpatrujesz \(\displaystyle{ {n \choose 2}}\) par.

Złożoność średnią nie jest łatwo obliczyć, musiałbyś znać zakres liczb i ich rozkład. A optymistyczna to \(\displaystyle{ O(1)}\) Trafiasz na odpowiednią parę za pierwszym razem. (Uwaga: Jeśli liczysz także wczytywanie danych to złożoność to \(\displaystyle{ O(n)}\).)

Rozumiem już teraz rozjaśniliście mi to dzięki za pomoc jak coś, to się jeszcze odezwę, musze to przetrawić -- 14 lis 2010, o 14:39 --To jeszcze raz ja

takie pytanie mi się jeszcze nasunęło
Czyli jak w innym zadanku mam w zapytaniu ile razy wykona się pewna linijka kodu, to również sprowadza się do policzenia złożoności obliczeniowej ? Dobrze myślę ? ?

Pozdrawiam

gizmo1985 pisze:Czyli jak w innym zadanku mam w zapytaniu ile razy wykona się pewna linijka kodu, to również sprowadza się do policzenia złożoności obliczeniowej ?

Nie zupełnie, złożoność obliczeniowa ujawnia jedynie stopień wielomianu,
ktróy mowi o asymptotycznej liczbie operacji uznanych za elementarne w danym zagadnieniu.
Można więc zgrubnie powiedzieć, że dla złożoności 0(n^2) dwukrotny wzrost wartości n powoduje czterokrotny wzrost liczby obliczeń.
Jednak jedynie zgrubie gdyż złożoność nie uwzgldnia niższych stopni wielominau oraz współczynników,
w związku z tym dwa algorytmy rozwiązania problemu mogą mieć identyczną złożoność,
a jednoczenie jeden może wykonywać się 1000 razy szybciej niż drugi.

gizmo1985 pisze:ile razy wykona się pewna linijka kodu?

To zależy w oglnym przypadku od stanu procesu, w szczególności dla pętli czy opercji warunkowych,
w związku z tym trudno w każdej sytuacji jednoznacznie odpowiedzieć na tak postawiony problem.

Załóżmy dla takiego przypadku ?
Wydaje mi się, że stwierdzenie ile razy wykona się linijka porównania sprowadzi się do policzenia złożoności obliczeniowej ? Czy nie ?

Jeśli Twoje przymyślenia zapisane stanowią pewnien logiczny ciąg rozumowania bez nieuprawnionych założeń, stanowią dowód.

Twoja funkcja
Sortowano(A, n)
for i=1 to n - 1 do
for j=1 to n - i do
if (A[j] > A[j+1]) then
Zamiana A[j] z A[j+1]

Rozpatrzymy kolejne linie
for i=1 to n - 1 do operacja1 // operacja1 wykona się n - 1 razy wzgldem pętli (for i) jest więc to złożoność liniowa O(n) wzgldem liczby elementów n

for j=1 to n - i do operacja2 // operacja2 wykona się n - 1 razy wzgldem pętli (for j) jest więc to złożoność liniowa O(n) wzgldem liczby elementów n

Jako że linia druga wykona się (n - 1) razy to operacja2 wykona się (n - 1) * (n - 1) razy.
Czyli porównanie wykona się (n - 1) * (n - 1) razy
Jest to złożoność kwadratowa wzgldem liczby elementów n.

Liczba zamian w przypadku optymistcznym wyniesie 0
w przypadku pesymistycznym może dążyć do (n - 1) * n / 2

Zauważ, że w drugiej linii jest n- i, a nie 1 To chyba coś zmieni

\(\displaystyle{ \sum_{i=0}^{n-1} n-i}\)

Nic innego mi nie przychodzi do głowy

NIe wiem też jak to dalej rozpisać ... a jutro zaliczenie

gizmo1985 pisze:Zauważ, że w drugiej linii jest n- i, a nie 1 To chyba coś zmieni

\(\displaystyle{ \sum_{i=0}^{n-1} n-i}\)

Nic innego mi nie przychodzi do głowy

NIe wiem też jak to dalej rozpisać ... a jutro zaliczenie

Masz rację to zmieni wynik z( n-1)*(n-1) na sumę ciągu którą podałeś czyli osttecznie będzie \(\displaystyle{ \frac{n \cdot (n-1)}{2}}\)
złożoność pozostaje kwadratowa, ale wykonujemy około 2 razy mniej operacji

czyli \(\displaystyle{ \sum_{i=0}^{n-1} \frac{n(n-1)}{2}}\)?