Witam otóż zacząłem się zastanawiać nad złożonością insertion sort ale właśnie problem w tym, że koszt całego algorytmu wyszedl mi
T(n) = 5n-2-2 Suma k=1 do n (t_{i}-1) i właśnie mam kłopot czy to jest dobrze...
0
0
Nie do końca rozumiem Twój zapis złożoności, więc sam wyliczę:
Pseudokod insertion sortu z wikipedii:
for i ← 1 to i ← length(A)-1
{
// A[ i ] is added in the sorted sequence A[0, .. i-1]
// save A[i] to make a hole at index iHole
item ← A[i]
iHole ← i
// keep moving the hole to next smaller index until A[iHole - 1] is <= item
while iHole > 0 and A[iHole - 1] > item
{
// move hole to next smaller index
A[iHole] ← A[iHole - 1]
iHole ← iHole - 1
}
// put item in the hole
A[iHole] ← item
}
Pętla for wykonuje się oczywiście równe n razy, czyli złożoność wynosi T(n) = n * zawartość pętli.
A ile czasu zajmuje wnętrze pętli? Nie bawiąc się w formalizmy, wykona się maksymalnie 'i' razy (gdzie i to obecna iteracja) - bo iHole zaczyna od i a kończy się kiedy jest równe zero. Z tego wynika że suma tego wynosi
Czyli złożoność jest równa
0
A mógłbyś mi oszacować koszty tego algorytmu?
0
@aynama koszty czego? o_O Kosz operacji zapisu/odczytu jest nie do oszacowania ze względu na optymalizacje na poziomie procesora (out-of-order-execution, read-ahead, cache, superskalarność, wielopotokowość)
0
No okej a znacie może jakieś zasady jak oblicza się taką złożoność obliczeniową??? Może jakąś łatwą książkę lub coś...abym mógł się w to powoli wprowadzić...
0
Cormen trochę o tym pisze we "Wprowadzeniu do algorytmów", ale w prostych przypadkach jak ten o który bylo pytanie to po prostu zlicza się ilość operacji tak jak zrobił to kolega @msm.