zlozonosc liniowa

Odpowiedz Nowy wątek
2011-05-25 12:06
porschelukas
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 (54n) 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?

Pozostało 580 znaków

2011-05-25 13:01
bo
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ą.

Pokaż pozostałe 10 komentarzy
patrząc z tej perspektywy większość algorytmów ma złożoność O(1), bo niemal zawsze istnieje maksymalny czas przetwarzania skończonego zbioru danych wejściowych, a co za tym idzie mniejsze, więc krócej przetwarzane zbiory danych robią z algorytmu O(1). moim zdaniem popełniasz gdzieś błąd logiczny. spójrz na quicksorta - dobrze wiemy, jaką ma złożoność obliczeniową. teraz, idąc tokiem Twojego rozumowania, dla każdej skończonej ilości danych staje się algorytmem o złożoności O(1), co jest, moim skromnym zdaniem, fałszem. - ŁF 2011-05-26 01:22
Dla ograniczonego z góry rozmiaru danych (tak jest w tym przypadku zadanie nie przewiduje na wejściu identycznych liczb) pytanie o złożoność jest pozbawione sensu. Pracowicie ustalimy, że ilość wykonywanych operacji = 35nn, tzn. złożoność jest O(nn). Ale n jest ograniczone z góry, powiedzmy n<=10<sup>8, zatem ilość operacji <=35n(10</sup>8), więc złożoność jest O(n), jeszcze raz stosujemy nierówność n<=10<sup>8 i dostajemy, że ilość operacji <= 35(10</sup>8)*(10^8), więc złożoność jest O(1). - bogdans 2011-05-27 12:04
czyli dla każdego skończonego zbioru danych wejściowych algorytm przetwarzający te dane w czasie skończonym jest algorytmem o złożoności O(1). z praktycznego punktu widzenia, jest to bez sensu . - ŁF 2011-05-27 13:24
Przywiązywanie nadmiernej wagi do złożoności rozumianej jako O(...) jest lekko bez sensu. Mamy dwa algorytmy, jeden jest O(1), wykona obliczenia dla każdego n w czasie 2578 lat (na obecnych komputerach), ale nie znamy jawnej zależności czasu wykonania od n, dla drugiego czas wykonania wynosi n*0,001 sekundy. Złożoność jest O(n). Rozmiar danych (tzn. n) nigdy nie przekroczy biliona. Nawet w najgorszym przypadku (n=bilion), czas wykonania to około 32 lat. Który algorytm jest lepszy? - bogdans 2011-05-27 14:34
zgadzam się z Tobą - patrz ostatni akapit mojej wypowiedzi cztery posty niżej. jednak taka złożoność jest istotną wskazówką, szczególnie jeśli dysponujesz także czasami wykonania dla kilku rzędów wielkości ilości danych. - ŁF 2011-05-27 15:04

Pozostało 580 znaków

2011-05-25 13:02
ŁF
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:


edytowany 2x, ostatnio: ŁF, 2011-05-25 13:15
Naprawdę pesymistyczną złożoność ma sortowanie przez losowe permutacje -- O(Inf). :P - rincewind 2011-05-28 09:08
W przypadku algorytmów randomizowanych pojęcie złożoności optymistycznej i pesymistycznej jest bezużyteczne. - Krolik 2011-06-06 16:26

Pozostało 580 znaków

2011-05-25 14:31
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.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
Jeżeli nie zależy na stabilności sortowania, to może być 54 stosy. - _13th_Dragon 2011-05-25 16:03

Pozostało 580 znaków

2011-05-25 17:58
porschelukas
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?

Pozostało 580 znaków

2011-05-25 18:07
ŁF
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.


edytowany 4x, ostatnio: ŁF, 2011-05-25 18:16

Pozostało 580 znaków

2011-05-25 20:59
porschelukas
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.

Pozostało 580 znaków

2011-05-25 21:56
ŁF
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]);

Pozostało 580 znaków

2011-05-25 22:19
porschelukas
0

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

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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