Prometheus. Масовий онлайн курс "Основи програмування". Лекція 8

  • Published on
    05-Aug-2015

  • View
    4.547

  • Download
    4

Embed Size (px)

Transcript

1. , , . Python, 8 , 2015 2. - 2 ' x = a a = b b = x a = a+b b = a-b a = a-b 3. 14 350 12312312312312 1965 7 500 23423423423423 1978 , - :-) 8 900 34343434343434 1985 8 600 53454756342109 1982 6 800 78328943905402 1976 8 600 74836732902100 1970 10 200 11567567567211 1971 4. 1 1 1 1 1 x Nx M 1 ~ 4*N*M + M 5. 2 ~ 4*N*log2N M ~ 4*N*log2N + M 6. 4*N*M + M 4*N*log2N + M 4*N*M + M 4*N*log2N + M 4*N*M 4*N*log2N M log2N M=6 ~ M>6 2 M64 64SUCCESS!!! f(n) = log2n 15. python 16. y = f(n) = n 2 y=f(n)=n3 y=f(n)=n4 : f(n) O(n 2 ) f(n) O(n3 ) f(n) O(n4 ) ... 2x4 + 5x3 + 3x2 + 4x 17. (bubble sort) , n2 18. "" (quicksort) n*log2n 19. y=f(n)=2n y=f(n)=3n y=f(n)=4n : f(n) O(2 n ) f(n) O(3n ) f(n) O(4n ) ... 20. abcdefghijklmnopqrstuvwxyz 26n ?????? (n=6) 266 = 308 915 776 = 308 916 = 5 148.6 = 85.8 = 3.6 2610 = 141 167 095 653 376 = 141 167 095 653 = 2 352 784 927.5 = 39 213 082 = 1 633 878 = 4 000 ?????????? (n=10) 21. abcdefghijklmnopqrstuvwxyz 26n ?????? (n=6) 266 = 308 915 776 = 308 916 = 5 148.6 = 85.8 = 3.6 2610 = 141 167 095 653 376 = 141 167 095 653 = 2 352 784 927.5 = 39 213 082 = 1 633 878 = 4 000 ?????????? (n=10) . 22. 8 88 = 64 4 426 165 368 23. , . example8_1.py 24. "" , 1 1 . example8_3.py 25. (backtracking) - 1 , , , , . example8_4.py 26. 4 (0, 1) (0, 0) (1, 3) (1, 2) (2, 5) (2, 4) (3, 7) (3, 6) . example8_5.py 27. () ' , , ( ). 28. ' 2 2 2 2 1 2 1 1 , "" , , ' . example8_6.py 29. ? '? ? ' ' ? ??? , ' , 30. f(n) O(k) f(n) O(n) f(n) O(n k ) f(n) O(n 2 ) ( ) f(n) O(k n ) f(n) O(log kn) 31. ! : "", 2015

Recommended

View more >