zlozonosc liniowa

0

Witam,
mam wątpliwość co do mojego algorytmu sortującego. Otóż program dostaje n liczb max sześciocyfrowych i wypisuje je nie rosnąco ze względu na sumę cyfr tych liczb. Ma to mieć złożoność liniową w zależności od n. Są jakieś algorytmy do sortowania w czasie liniowym, ale akurat to zadanie wg mnie jest najłatwiej zrobić w ten sposób, że zliczam sumy cyfr tych liczb z wejścia. Max suma to będzie 54 dla liczby 999999. I teraz tak zapuszczam pętlę 54 razy gdzie przy każdym jej obrocie sprawdzam czy któraś z liczb ma taką sumę cyfr (co obrót ta suma będzie wynosiła mniej). No i teraz tak wychodzi na to że złożoność to jest (54*n) czyli niby liniowo, więc jest dobrze. Program będzie mało wydajny. Żeby nieco poprawić wydajność można sprawdzić która liczba ma największą sumę cyfr i od tej liczby zacząć przeglądać całą tablicę odpowiednią ilość razy. Tylko teraz złożoność to wychodzi (max_suma_cyfr * n) i nie wiem czy to dalej jest liniowe?

0

Dziwnie liczyć złożoność, przy Twoim sposobie złożoność jest 54*1000000, tzn. O(1). Ograniczenie na zakres wprowadzanych danych (liczby sześciocyfrowe) nie wpływa na złożoność obliczeniową.

0

nie czas liniowy, tylko liniowa złożoność obliczeniowa (O(n)). algorytmy sortujące o takiej złożoności działają tylko w specyficznych przypadkach:

0

Robisz tablicę 54 list jednokierunkowych.
Liczby wstawiasz na koniec odpowiedniej listy.
Po zakończeniu dodawania wszystkich scalasz te listy, podpinając kolejną na koniec poprzedniej.
I masz liniowy algorytm.

0

Dzięki za zainteresowanie tematem, chociaż trochę się już pomieszałem.
Może trochę sprostuje, ŁF mówił że suma cyfr liczby 10, 1000, 100 jest mniejsza niż liczby 9. A nie jest tak? Co jeśli będę miał kilka takich samych liczb? Zapomniałem dodać, że zadanie nie przewiduje na wejściu identycznych liczb, owszem suma może być taka sama, wtedy wypisywane mają być w kolejności jakiej zostały wpisane na wejściu. Więc po wypisaniu pierwszej pasującej do sumy nie przerywam pętli tylko jadę do końca. W kodzie wygląda to tak:

//dzialam na tablicy stuktur, ktora posiada pola suma i id typu calkowitego
	for(max=54; max>=0; max--)		
		for(i=0; i<n; i++)
			if(tab[i].suma == max)
				printf("%d\n", tab[i].id);

Co do wydajniejszego sortowania to, wiem że da się to zrobić countingsortem czy jakoś tak, nawet bym potrafił, ale po co jeśli akurat ten kod spełnia wymogi czasowe wykonania sie;) Użycie sortowania typu quicksort lub heapsort byłoby wydajne lecz mam wyraźnie w treści zadania napisane:

Losy powinny zostać posortowane algorytmem o liniowej złożoności czasowej.

Co do list, to niestety nie potrafię ich robić, mam zamiar w wakacje się nauczyć;)

Zależy mi głównie na odpowiedzi, czy mój algorytm spełnia złożoność liniową w zależności od n czyli liczby podanych liczb. Rozumiem że, tak?

0

tak.

ale ciąg liczb 52, 2000, 44, 9, 10, 39, 56 "posortowany" Twoim algorytmem będzie mieć kolejność 10, 2000, 52, 44, 9, 56, 39. nie można nazwać tego sortowaniem według wartości. Twój algorytm wykonuje w czasie liniowym "sortowanie liczb według wartości sumy ich cyfr", a nie "sortowanie liczb według ich wartości".

zastanów się jeszcze nad sensem budowania algorytmu O(n), gdzie jedna iteracja trwa kilkadziesiąt razy dłużej od O(nlogn) - bo tyle dodatkowych pętli robisz. Twój algorytm będzie wydajniejszy dopiero dla ciągów o długości liczonej w setkach miliardów (O(54n) < O(nlogn) => nlogn > 54*n => log(n) > 54 => n > 2^54). zobacz jak działa countingsort i go zaimplementuj.

0

hmm... chyba się nie jasno wyraziłem, numery ID mają być posortowane i wypisane malejąco według sumy ich cyfr, jeśli suma cyfr kilku ID jest taka sama pierwszy ma być wypisany ten który był wcześniej wpisany. Okej, ale skoro to jest liniowo zrobione to fajnie;) i jeszcze mam pytanie, sprawdzenie wcześniej która suma cyfr liczby ID jest największa i kręcenie pętlą od tej sumy nie popsuje mi złożoności, np jeśli ID 42343 ma największą sumę cyfr z pośród wszystkich podanych to kręcenie tą pętlą od 16? Dokładnie chodzi mi o to że złożoność będzie wtedy zależna jeszcze od tego które ID ma największą sumę cyfr a wartość ta może być różna, zaś jeśli podam 54to będzie tylko zależało od n i rosło liniowo.

0

ha ha ha, nie, wyraziłeś się jasno, to ja po raz kolejny nieuważnie przeczytałem posta ; )
tylko że robisz mnóstwo niepotrzebnych przebiegów po tablicy z liczbami - 54 * n. da się to zrobić w n: 54-elementowa tablica wypełniona np. zerami, do niej na odpowiednie miejsca wpisujesz podawane liczby, a przy wypisywaniu wyniku jedziesz petlą po tej tablicy i wypisujesz tylko liczby większe od zera. tablicę można zainicjować czymś innym od zera, -1 czy czymś siedmiocyfrowym.
coś w stylu:

inicjuj_tablicę(-1);
dopóki (mam_liczbę)
  tablica[wartość_sumy_cyfr(liczba)] = liczba;

od indeks = 1 do 54
  jeśli (tablica[indeks] > -1)
    wypisz(tablica[indeks]);
0

dzięki wielkie, będę kombinował;)

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