void radixSort(int *tab, int n, int max) {
int i, j, m, p = 1, index, temp, count = 0;
list<int> zliczanie[10]; // lista o rozmiarze 1-10 (lub inna w zaleznosci od systemu liczbowego)
for(i = 0; i< max; i++) {
m = pow(10, i+1); //
p = pow(10, i); // dzieli liczbe
// na kolejne rzedy
for(j = 0; j<n; j++) { // jednosci dziesiatek itd.
temp = tab[j]%m; //
index = temp/p; // wyznacza liczby z zakresu od 1-10(lub inna w zaleznosci od systemu liczbowego)
zliczanie[index].push_back(tab[j]); //zlicza ile liczb ma dana cyfre na danym rzedzie
}
count = 0;
for(j = 0; j<10; j++) { //petla ktora usuwa z pomocniczej tablicy
while(!zliczanie[j].empty()) { //kolejne liczby wedlug tego jak zostaly
tab[count] = *(zliczanie[j].begin()); //posortowane ich cyfry na danym
zliczanie[j].erase(zliczanie[j].begin()); //rzedzie jednosci, dziesiatek itd.
count++;
}
}
}
}
Witam,
Potrzebuje podać złożoność obliczeniową danej funkcji pomocniczej, wiem że w notacji wynosi \(\displaystyle{ O(d(n+b)}\) jednak chce ją podać bardziej szczegółowo i wychodzi mi coś takiego: \(\displaystyle{ 3+2d(2n+b) = O(d(n+b)}\)
zliczałem tylko operacje przypisania i nie wiem czy czegoś tu nie brakuje
Ostatnio zmieniony 30 maja 2019, o 19:13 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód:Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Obliczenie faktycznej liczby operacji nie jest trywialne. Podany program napisany jest w C++, w związku z tym wykonywana liczba operacji jest zależna od tego jak działa kompilator.
Na przykład: jeżeli podczas kompilacji kompilatorem g++ używasz opcji -O3, pętla for może zostać zwektoryzowana. Oznacza to, że program będzie korzystał z rejestrów multimedialnych, za pomocą których można wykonać "kilka" operacji arytmetycznych na raz. Na przykład, liczba 32-bitowa może zostać cztery razy wpisana do 128-bitowego multimedialnego rejestru AVX. W związku z tym, w najprostszym przypadku, użycie wektoryzacji spowoduje wykonywanie 4 razy mniej operacji arytmetycznych, liczba odczytów oraz zapisów w pamięci pozostaje jednak taka sama. Zauważ, że nie wpływa to na złożoność obliczeniową algorytmu.
Z drugiej jednak strony, nie każdą operacje w pętli zwektoryzować się da, dlatego należałoby spojrzeć na asm, aby zobaczyć co kompilator właściwie zrobił.
Ponadto, korzystasz z metod oraz klas, które wykonują stałą liczbę operacji (która również nie ma wpływu na złożoność). Funkcja pow nie koniecznie wykonuje jedną operacje arytmetyczną. Trudno zgadywać ile operacji odczytu oraz zapisu jest wykonywane podczas jej realizacji, ale żaden z powyższych faktów nie ma nic wspólnego ze złożonością obliczeniową.
Dlatego złożoność obliczeniowa jest cechą algorytmu, a liczba wykonywanych operacji jest cechą konkretnej implementacji tego algorytmu.
