Лекция №4. Асимтотическая нотация. Предмет "Структуры и алгоритмы обработки данных"

  • Published on
    07-Jul-2015

  • View
    669

  • Download
    1

Embed Size (px)

Transcript

<ul><li> 1. . .. : , www.grebenshikov.ru </li></ul> <p> 2. O - : f (n) = O(g(n)) (c &gt; 0, n0 &gt; 0 0 f (n) c g(n), n n0)O(g(n)) = {f (n) : c &gt; 0, n0 &gt; 0 0 f (n) c g(n), n n0}: 2n2 = O(n3) 2n2 O(n3) 1 3. f (n) = n3 + O(n2) (h(n) O(n2), f (n) = n3 + h(n)) 2 4. - : (g(n)) = {f (n) : c &gt; 0, n0 &gt; 0 0 c g(n) f (n), n n0} : n = (lg(n)) 3 5. - : f (n) : c1 &gt; 0, c2 &gt; 0, n0 &gt; 0 (g(n)) = c1 g(n) f (n) c2 g(n), n n0(g(n)) = O(g(n)) (g(n)) 4 6. : T (n) = 4T (n/2) + n 1. () 2. 3. 5 7. : T (n) = 4T (n/2) + n: T (n) = O(n3): T (1) = (1) &lt; c &lt; c n3 : T (k) c k3, k &lt; n 6 8. :n T (n) = 4T +n2 n 3 4c+n 21= cn3 + n2= cn 3 ( 1 cn3 n) 2 1 cn3, cn3 n 0 2 : (c 1, n 1)7 9. : T (n) = O(n2): T (1) = (1) &lt; c &lt; c n2 : T (k) c k2, k &lt; n 8 10. :n T (n) = 4T +n2 n 2 4c+n 2 = cn2 + n = cn2 (n) : n &gt; 09 11. : T (k) c1 k2 2 k, k &lt; n :n T (n) = 4T +n2 n 2 n= 4c1 c2 +n 2 2= c1n2 + (1 2c2)n= c1n2 2c2n (1 + c2)n c1n2 c2n, c2 1: T (1) = (1) &lt; c1 c210 12. :(c2 1)(c1 c2)11 13. T (n) = T (n/4) + T (n/2) + n212 14. 13 15. C: (1 + 5/16 + 25/256 + . . . + 5k /16k + . . .)n2 =?: (1 + 1/2 + 1/4 + 1/8 + 1/16 + . . .) == (1 + 1/2k + . . .)= 1.1111111(1)=2 1/2k &gt; 5k /16k (1 + 5k /16k + . . .)n2 &lt; 2n2 (1 + 5k /16k + . . .)n2 = O(n2) 14 16. T (n) = aT (n/b) + f (n)a 1, b &gt; 1, f (n) (f (n) &gt; 0, n &gt; n0) 15 17. 1. f (n) = O(nlogba ), &gt; 0 T (n) = (nlogba) 2. f (n) = (nlogba) T (n) = (nlogbalog(n)) 3. f (n) = (nlogba ), &gt; 0, af (n/b) cf (n), c &lt; 1, n &gt; n0 T (n) = (f (n))16 18. T (n) = 4T (n/2) + nnlogba = nlog24 = n2 - 1- : T (n) = (n2) 17 19. T (n) = 4T (n/2) + n2 - 2- : T (n) = (n2log(n))18 20. T (n) = 4T (n/2) + n3 - 3- : T (n) = (n3)19 21. T (n) = 4T (n/2) + n3/log(n): - . 20 22. : logb n1 : (nlogba) +aj f (n/bj ) j=0 21 23. : 1. f (n). . 2. (nlogba). . 3. . f (n). 22 24. ., ., ., . -: , 2- . - . : - , 2007. .87-139. 23 </p>

Recommended

View more >