Projekt algorytmu i złożoność obliczeniowa

[gizmo1985]

Witam
MAm takie zadanko z którym do pewnego stopnia (chyba) się uporałem

Kod: Zaznacz cały

Dana jest tablica [1...n] zawierająca n liczb. Zaprojektuj algorytm sprawdzający,  czy w  tablicy A są dwie liczby dające w sumie wartość x, a następnie określ jego złożoność obliczeniową 

Spłodziłem do tego taki pseudokod:

Kod: Zaznacz cały

 for i=0 to n-1 do
for j=0 to n-1 do
if (j!=i AND A[j] + A[i]==x) 
return true; 

return false;

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ń ?

[abc666]

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

[PMichalak]

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,

[gizmo1985]

abc666, a jak inaczej proponujesz ? bo nie kumam ?

[abc666]

Kod: Zaznacz cały

for i=0 to n-1 do
   for j=i+1 to n-1 do
      if (A[j] + A[i]==x)
         return true;

return false;

[gizmo1985]

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ą?

[PMichalak]

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)}\).)

[gizmo1985]

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

[smiechowiec]

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.

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.

[gizmo1985]

Kod: Zaznacz cały

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

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 ?

[smiechowiec]

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

[gizmo1985]

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

[smiechowiec]

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

[gizmo1985]

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

[smiechowiec]

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