Złożoność liniowa uporządkowanych liczb wejściowych w sortach i minimach

0

Dla przykładu optymistycznego kiedy mielibysmy jakis uporządkowany zbiór np.1,2,3,4,5,6,7,8
to czy zlozonosc jest O(n) czy O(n^2) no bo przeciez jakby zliczyc porównania to powinna byc notacja kwadratowa czy sie myle?
moja prosta implementacja insertion sort:

for(i=1;i<=n;++i )
    for(i=j;j>1;--j )
        if(a[j]<a[j-1])
        swap(a[j],a[j-1])

ale jak byśmy mieli algorytm minimum dla tego samego zbioru i mielibyśmy na początku min=1 to zlozonosc w przypadku optymistycznym jest O(1) czy O(n)

0 
for(i=j;j>1;++j )

prędzej

for(j=i; j>1; --j )

Masz O(n2) porównań.

Przecież algorytm szukania minimum, który polega na przejściu przez całą tablicę, zawsze wykonuje tyle samo roboty niezależnie od danych. To że dane są posortowane nie ma żadnego znaczenia, bo skąd algorytm miałby o tym wiedzieć? Więc pesymistyczny = optymistyczny = O(n).

0

Na temat pisz w wątkach, a nie komentarzach.

http://edu.pjwstk.edu.pl/wyklady/asd/scb/asd01/main01_p5.html

W każdym algorytmie można wyróżnić pewną operację istotną dla rozwiązywanego zadania. Taką operację nazwiemy dominującą. Mówimy, że koszt czasowy algorytmów mierzymy liczbą operacji dominujących. Wybór operacji dominującej zależy od problemu i wybranego rozwiązania. W problemie mnożenia macierzy za operacje dominujące można uznać operacje arytmetyczne +, *. W problemie wyszukiwania elementu w zbiorze, operacją dominującą jest równość. W problemie sortowania operacją dominującą jest najczęściej porównywanie elementów, ale można też przyjąć operację przestawiania elementów.

1

Twoja implementacja jest niepoprawna. Miejsca dla elementu, który chcesz wstawić, szuka się do momentu kiedy natrafi się na miejsce, gdzie nie można nie trzeba robić swapa. Założenie jest takie, że Ty wiesz, że "po lewej" już masz wszystko posortowane, więc jeśli raz napotkasz coś mniejszego od siebie, to dalej (w lewo) też tak będzie. Stąd właśnie w optymistycznym przypadku (posortowany ciąg), zawsze w jednym kroku uznasz, że już dalej nie ma sensu. Stąd przejdziesz tablicę, tylko raz. Ty wykonujesz o(n^2) operacji tak czy siak.

0
masterkwi napisał(a):

Dla przykładu optymistycznego kiedy mielibysmy jakis uporządkowany zbiór np.1,2,3,4,5,6,7,8
to czy zlozonosc jest O(n) czy O(n^2) no bo przeciez jakby zliczyc porównania to powinna byc notacja kwadratowa czy sie myle?
moja prosta implementacja insertion sort:

for(i=1;i<=n;++i )
    for(i=j;j>1;--j )
        if(a[j]<a[j-1])
        swap(a[j],a[j-1])

ale jak byśmy mieli algorytm minimum dla tego samego zbioru i mielibyśmy na początku min=1 to zlozonosc w przypadku optymistycznym jest O(1) czy O(n)

tak, w tej postaci (implementacji) ma n^2 zawsze.

0

Przyjmuje za operację dominującą porównania
bo na przykład jak mamy taki kod:

void bubble_sort(int a[],int n)
{
    int i,j;
    int flag=1;
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-i-1;j++)
        {

            if(a[j]>a[j+1])
            {   flag=0;
                swap(a[j],a[j+1]);
            }
        if(flag==1)
        {
            cout<<"already sorted"<<endl;
            break;
        }
        }
     
    }
    for(i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}

ale nie byłoby założenia że jest posortowane

     if(flag==1)
        {
            cout<<"already sorted"<<endl;
            break;
        }

to byłoby w optymistycznym przypadku O(n^2) ?

Ale jakbyśmy przyjęli operacje dominującą zamiany to nawet dla np. 1,2,3,4,5,6,7,8
dla kodu bez

     if(flag==1)
        {
            cout<<"already sorted"<<endl;
            break;
        }

byłoby O(n) i dla tego mam problem bo kiedy przyjmujemy rózne operacje(porównywanie lub zamiana) za dominujące to mamy różne wyniki

1

Operację dominującą wybiera się po to, żeby sobie ułatwić analizę. Złożoność obliczeniowa jest jedna i tylko od tego czy poprawnie przeprowadzisz analizę zależy to, czy wyjdzie Ci ona poprawna. Kod który wrzuciłeś, znowu jest jakiś niekompletny (tzn. wrzuciłeś kod z flagą nieużywaną, potem wrzuciłeś jakiegoś ifa, który nie wiadomo gdzie ma trafić).

Możesz spróbować policzyć kazdą operację z osobna (swapy, ify) i wybrać tę, której jest najwięcej. Pamiętaj tylko, że nie każda gałąź ifa się wykonuje, więc musisz jakoś szacować ile razy to się stanie. Algorytm, który wrzuciłeś (bubble) ma złożoność O(n^2) bo jakiekolwiek operacje (if czy swap) są tak głęboko w pętlach, że samo iterowanie zajmuje tyle czasu.

Jako ogólna rada: liczenie obiegów pętli jest dość dobrą metodą szacowania złożoności jeśli możemy założyć, że w ciele pętli wykonuje się stała liczba operacji. W twoim wypadku obiegów pętli będzie O(n^2).

2

Tu masz implementacje która ma optymistycznie O(n) https://pl.wikipedia.org/wiki/Sortowanie_przez_wstawianie

1

W rozwiązaniu przytoczonym przez topik92 kluczowe jest to, że została użyta pętla while, której ciało nie zostanie w ogóle wykonane przy posortowanej tablicy (bo A[j] > klucz będzie zawsze fałszem).

Tak jeszcze gwoli ściśłości, o ile na forum wygodnie używa sie notacji dużego O do opisywania zlożoności, to przy dolnych granicach (najlepszych przypadkach) powinno się używać raczej notacji z dużym omega.

0
Kele napisał(a):

Operację dominującą wybiera się po to, żeby sobie ułatwić analizę. Złożoność obliczeniowa jest jedna i tylko od tego czy poprawnie przeprowadzisz analizę zależy to, czy wyjdzie Ci ona poprawna. Kod który wrzuciłeś, znowu jest jakiś niekompletny (tzn. wrzuciłeś kod z flagą nieużywaną, potem wrzuciłeś jakiegoś ifa, który nie wiadomo gdzie ma trafić).

Możesz spróbować policzyć kazdą operację z osobna (swapy, ify) i wybrać tę, której jest najwięcej. Pamiętaj tylko, że nie każda gałąź ifa się wykonuje, więc musisz jakoś szacować ile razy to się stanie. Algorytm, który wrzuciłeś (bubble) ma złożoność O(n^2) bo jakiekolwiek operacje (if czy swap) są tak głęboko w pętlach, że samo iterowanie zajmuje tyle czasu.

Jako ogólna rada: liczenie obiegów pętli jest dość dobrą metodą szacowania złożoności jeśli możemy założyć, że w ciele pętli wykonuje się stała liczba operacji. W twoim wypadku obiegów pętli będzie O(n^2).

Mógłbyś podać przykład kiedy jakaś gałąź ifa się nie wykonuje i wtedy nie liczymy tego jako operacji która zwiększyłaby złożoność?

0

W Twoim kodzie to nie zadziała w ogóle. W kodzie przesłanym przez topik92 masz pętle while, której ciało nie wykona się nigdy dla tablicy posortowanej niemalejąco (np. [1, 2, 3, 4, 5, 6]), bo zawsze będzie A[j] <= klucz.

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