złożoność algorytmiczna

Witam,
napisałem taki program, który sortuje wektor od 0 do 1. Jaka jest złożoność algorytmiczna i czas obliczeniowy? Muszę podać to w formie wykresu, ale nie wiem jak mam to zrobić. Proszę o podpowiedzi. Dodam, że jestem samoukiem, więc wybaczcie za głupie błędy. W załączniku przesyłam schemat blokowy.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <cstdio>
#include <ctime>

using namespace std;
int main()
{
    clock_t start, koniec;
    start = clock();
    int n;
    cout << "Podaj dlugosc tablicy:\n ";
    cin >> n;
    srand(time(NULL));
    int tab[n];
    for (int i = 0; i < n; i++) {
        tab[i] = rand() % 2;
    }
  cout << "\nTablica przed posortowaniem: \n";
    for (int i = 0; i < n; i++) {
        cout << tab[i] << " ";
    }
    int p, q, mix;
    p = 0;
    q = n - 1;
    while (p < q) {
        while (tab[q] == 1)
            q--;
        while (tab[p] == 0)
            p++;
        if (p < q) {
            mix = tab[p];
            tab[p] = tab[q];
            tab[q] = mix;
            p++;
            q--;
        }
    }	 
    cout << "\nPodana, posortowana tablica to:\n";
    for (int k = 0; k < n; k++) {
        cout << tab[k] << " ";
    }
    koniec = clock();
    cout << "\nczas: " << (koniec - start) << " milisekund";
    ;
} 

Mierz czas wykonania dla zbiorów o różnych wielkościach (10, 100, 1000, 1e4, 1e5, 1e6, 1e7, 1e8). Wyniki przedstaw w formie wykresu.

kq napisał(a):

Mierz czas wykonania dla zbiorów o różnych wielkościach (10, 100, 1000, 1e4, 1e5, 1e6, 1e7, 1e8). Wyniki przedstaw w formie wykresu.

wykonuję testy na zbiorze 1000 elementów, ale za każdym razem czas jest inny nawet o kilka sekund. złożoność jest na pewno liniowa, ale jak to wytłumaczyć.

1. Mierzysz niepoprawny fragment kodu - masz mierzyć tylko sortowanie. Ty również mierzysz wprowadzanie i generowanie danych.
2. Dla wygody dane powinieneś wczytywać z pliku/generować losowo. Możliwe, że już to robisz za pomocą przekierowania strumienia, ale wątpię (wielkość tablicy).
3. Używasz niepoprawnej metody mierzenia czasu. Piszesz w C++, użyj <chrono> http://en.cppreference.com/w/cpp/chrono masz nawet przykład
4. Aby pokazać zależność t(n) musisz obliczyć to dla różnych n! A nie dla stałego...

dane do tablicy wprowadzane są losowo użytkownik podaje tylko długość jaką chce. co do czasu to samo sortowanie zawsze jest poniżej 1 sekundy. i nie wiem jak obliczyć złożoność.

Czyli jedną z rzeczy, które obecnie (nieporadnie, bo clock dość słabe do tego jest) mierzysz jest czas reakcji użytkownika i czas generowania danych.

http://en.cppreference.com/w/c/chrono/clock poczytaj, zobacz przykład.

Złożoność: otrzymałeś odpowiedź powyżej. Zastosuj się.

a jeśli bym użył timera w c++??
a jak obliczyć złożoność bo nie wiem?

Generalnie to złożoność się liczy w oparciu o teorie prawdopodobieństwa analizując algorytm.
Żadnym pomiarem czasu złożoności nie policzysz - możesz jedynie zrobić sobie wykres i na jego podstawie zgadywać.
Lub znaleźć obliczenia dla tego algorytmu zrobione przez innych - dla quicksort oczekiwane O(n*log(n))

TIMER jest do zrobienia wykresu, a nie wiem jak obliczyć złożoność obliczeniową.

@bart3195 policz ile razy program wykona operacje porównania oraz przypisania w zależności od rozmiaru tablicy. Na przykład coś takiego:

    for (int i = 0; i < n; i++) {
        tab[i] = rand() % 2;
    }

Wymaga dokładnie n operacji przypisania więc złożoność tego fragmentu to O(n). Policz analogicznie dla reszty.

Czyli złożoność to 4n? bo 4 razy program przechodzi przez całą tablicę. jeśli nie było by wypisywania danych to 2n? zgadza się?

Ani trochę. Pokaż mi gdzie wg ciebie następują te 4 przejscia przez tablicę. Poza tym taki szczegół, notacja O usuwa czynniki stałe i niskich rzędów, więc np. O(4n) = O(n) oraz np. O(n + 10) = O(n)

Reasumując złożoność to O(n). czyli liniowa. a wykres zrobię dzięki timerom, ale tylko sortowanie czy też wypisywanie danych?

Literówka ;] Miało być ani trochę. Złożoność nie jest liniowa. Not even close.

to ja już nic nie rozumiem :((

Nieśmiało podrzucam definicje notacji dużego O, bo chyba niektórzy nie rozumieją.

mój program ma złożoność O(n) i nie jest liniowy, ale jak to uzasadnić?

Twój program nie ma złożoności O(n). Ale jak testujesz to na tablicach rozmiaru kilku elementów to nic nie zobaczysz na tych swoich wykresach. Ba, dopiero pewnie jak wyskoczysz z cache procesora to coś ciekawego będzie widać, więc musiałbyś mieć przynajmniej 8MB danych więc ~2 mln elementów.

TO ja już nie wiem jak to zrobić, ktoś pomoże? wykres do programu i złożoność. Ja naprawdę nie rozumiem tego

@bart3195 słabo mi.

1. Nie alokuj danych na stosie tylko na stercie za pomocą new int[n] bo tablice powyżej kilku MB nie wejdą ci na stos.
2. A po co chcesz te dane wypisywać w ogóle? o_O

Dana jest nieuporządkowana tablica jednowymiarowa (wektor) o długości n. Tablica ta zawiera tylko dwa rodzaje elementów. Posortuj tą tablicę w ten sposób, aby złożoność obliczeniowa algorytmu była jak najmniejsza. Sortowanie wykonaj za pomocą przestawiania odpowiednich elementów i bez używania pomocniczej tablicy. Np. jeśli tablica jest typu całkowitego i zawiera tylko elementy o wartości 0 i 1 , {0,1,1,0, .....0,1,0} to po uporządkowaniu jest postaci {0,0,0,........,1,1,1}

Takie mam zadanie i się z nim nie mogę uporać

czas mierzę tylko sortowania ale nie umiem użyć timera :(

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <cstdio>
#include <ctime>

using namespace std;
int main()
{
    clock_t start, koniec;
     long long int n;
    cout << "Podaj dlugosc tablicy:\n ";
    cin >> n;
    srand(time(NULL));
    long long int tab[n];
    for (int i = 0; i < n; i++) {
        tab[i] = rand() % 2;
    }
  cout << "\nTablica przed posortowaniem: \n";
    for (int i = 0; i < n; i++) {
        cout << tab[i] << " ";
    }
    int p, q, mix;
    p = 0;
    q = n - 1;
     start = clock();
    while (p < q) {
        while (tab[q] == 1)
            q--;
        while (tab[p] == 0)
            p++;
        if (p < q) {
            mix = tab[p];
            tab[p] = tab[q];
            tab[q] = mix;
            p++;
            q--;
        }
    }	   
	koniec = clock();
    cout << "\nPodana, posortowana tablica to:\n";
    for (int k = 0; k < n; k++) {
        cout << tab[k] << " ";
    }
    cout << "\nczas: " << (koniec - start) << " milisekund";
    ;
}

Zamiast long long int tab[n]; (super pomysł, podmienić VLA intów na long longów :D )

#include <vector>

i std::vector<int> tab(n);

Przy takiej sytuacji zliczyłbym elementy mniejszej wartości, następnie wypełniłbym część tabeli mniejszą wartością, a drugą część drugą. Powinno być szybsze niż sortowanie, a efekt ten sam.

Polecenie zadania jest nieprecyzyjne, zeby nie powiedzieć że błędne.
Posortuj tą tablicę w ten sposób, aby złożoność obliczeniowa algorytmu była jak najmniejsza co sugeruje Zliczanie, szczególnie ze mamy tak mocno ograniczony zakres danych -> tylko 0 i 1 ale potem jest Sortowanie wykonaj za pomocą przestawiania odpowiednich elementów co oznacza ze jednak autor chciałby jakiegoś Merge Sorta...
QuickSorta bym odrzucił bo o ile empirycznie może być szybszy, o tyle pesymistycznie może dać O(n²).

Twój problem nie jest z timerem ale z tym że:

1. Nie rozumiesz jak szybko komputer potrafi liczyć
2. Nie rozumiesz że wypisywanie na ekran zajmuje wielokrotnie więcej czasu niz sortowanie danych
3. Nie rozumiesz jak zbudowana jest pamieć procesu który uruchamiasz, że jest podzielona na stos i stertę.

Ja bym obstawiał heapsort.

A powie mi ktoś wprost jaka jest złożoność tego algorytmu?

bart3195 napisał(a):

A powie mi ktoś wprost jaka jest złożoność tego algorytmu?
Czy ty czytasz co tobie odpowiadają:

1. http://4programmers.net/Forum/1220190
2. http://4programmers.net/Forum/1220373
   Jak bardziej wprost ci powiedzieć?

Mały OT, zetknęliście się wcześniej z terminem złożoność algorytmiczna?

Złożoność tego algorytmu wynosi n, ponieważ tylko raz przechodzimy przez tablicę (tak powiedział wykładowca mój) i jest to funkcja LINIOWA