Лекция №9. Сортировка. Часть №1. Предмет "Структуры и алгоритмы обработки данных"

  • Published on
    20-Jun-2015

  • View
    1.437

  • Download
    8

Embed Size (px)

Transcript

<ul><li> 1. . .. : . 1. , www.grebenshikov.ru </li></ul> <p> 2. - - ( - ). - . - : - - 1 3. : N a1, a2, . . . , aN: , .. - ap1 , . . . , apN , kp1 kp2 . . . k pN .2 4. - . kpi = kpj i &lt; j, pi &lt; pj .3 5. (); ; ; ; ; .4 6. 40 |51 838 90 14 263 40 51 |838 90 14 263 840 51 |38 90 14 263 838 40 51 |90 14 263 838 40 51 90 |14 263 814 38 40 51 90 |263 2814 38 40 51 90 |63 2814 38 40 51 63 90 |5 7. 6 8. : - :C(N ) = 1 + 2 + 3 + . . . + N 1 = N (N 1) = O(N 2) 2 :M (N ) = N cdot(N 1) + 2 (N 1) = O(N 2) 2 : T (N ) = C(N ) + M (N ) = O(N 2)7 9. . : C(N ) = O(N log(N )) : M (N ) = O(N 2) : T (N ) = C(N ) + M (N ) = O(N 2) 8 10. . - . . 9 11. | 40 51 838 90 14 263 2 |40 51 838 90 14 63 2 8|40 51 38 90 14 63 2 814 |40 51 38 90 63 2 814 38 |40 51 90 63 2 814 38 40 |51 90 63 2 814 38 40 51 |90 63 2 814 38 40 51 63 |90 2 814 38 40 51 63 90 |10 12. 11 13. : - :C(N ) = (N 1) + (N 2) + . . . + 1 = N (N 1) = O(N 2) 2 :M (N ) = N 1 = O(N ) : T (N ) = C(N ) + M (N ) = O(N 2)12 14. - : (, , heap). h1, . . . , hn hi : (2i n hi h2i) h2i ; (2i + 1 n hi h2i+1) h2i+1 ; h n +1, . . . , hn -2 . 13 15. 15- 14 16. 12- 15 17. 1. . 2. . . . .16 18. 17 19. 18 20. 19 21. 20 22. (1 2)21 23. (2 2)22 24. : O(log(N ), .. N O(log(N )) C(N ) = 2 M (N ) : O(N log(n)) : O(N log(n)) : T (N ) = O(N log(n)) 23 25. . . 24 26. : - :C(N ) = (N 1) + (N 2) + . . . + 1 = N (N 1) = O(N 2) 2 :M (N ) = C(N ) = O(N 2) : T (N ) = C(N ) + M (N ) = O(N 2)25 27. . -. .26 28. .., .. : -, : . / -. . -. , 2006. .2. 58 . .26-41. ., ., . . - . : , 2000..228-234, 244-246. ., ., ., . -: , 2- . - . : - , 2007. .173-197.27 29. , , 3. , 2- . - . : , 2000. .92-180. </p>

Recommended

View more >