TAILIEUCHUNG - Giáo trình phân tích khả năng vận dụng kĩ thuật đánh giá giải thuật theo phương pháp tổng quan p2

Tham khảo tài liệu 'giáo trình phân tích khả năng vận dụng kĩ thuật đánh giá giải thuật theo phương pháp tổng quan p2', kỹ thuật - công nghệ, tự động hoá phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Giải thuật Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương trình thay vì xét chính bản thân thời gian thực hiện. Cho một hàm T n T n gọi là có độ phức tạp f n nếu tồn tại các hằng C N0 sao cho T n Cf n với mọi n N0 tức là T n có tỷ suất tăng là f n và kí hiệu T n là O f n đọc là ô của f n Ví dụ 1-5 T n n 1 2 có tỷ suất tăng là n2 nên T n n 1 2 là O n2 Chú ý O n O f n với C là hằng số. Đặc biệt O C O 1 Nói cách khác độ phức tạp tính toán của giải thuật là một hàm chặn trên của hàm thời gian. Vì hằng nhân tử C trong hàm chặn trên không có ý nghĩa nên ta có thể bỏ qua vì vậy hàm thể hiện độ phức tạp có các dạng thường gặp sau log2n n nlog2n n2 n3 2n n nn. Ba hàm cuối cùng ta gọi là dạng hàm mũ các hàm khác gọi là hàm đa thức. Một giải thuật mà thời gian thực hiện có độ phức tạp là một hàm đa thức thì chấp nhận được tức là có thể cài đặt để thực hiện còn các giải thuật có độ phức tạp hàm mũ thì phải tìm cách cải tiến giải thuật. Vì ký hiệu log2n thường có mặt trong độ phức tạp nên trong khôn khổ tài liệu này ta sẽ dùng logn thay thế cho log2n với mục đích duy nhất là để cho gọn trong cách viết. Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến hiệu quả của thời gian thực hiện của chương trình nên ta có thể xem việc xác định thời gian thực hiên của chương trình chính là xác định độ phức tạp của giải thuật. CÁCH TÍNH ĐỘ PHỨC TẠP Cách tính độ phức tạp của một giải thuật bất kỳ là một vấn đề không đơn giản. Tuy nhiên ta có thể tuân theo một số nguyên tắc sau Qui tắc cộng Nếu T1 n và T2 n là thời gian thực hiện của hai đoạn chương trình P1 và P2 và T1 n O f n T2 n O g n thì thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là T n O max f n g n Ví dụ 1-6 Lệnh gán x 15 tốn một hằng thời gian hay O 1 Lệnh đọc dữ liệu READ x tốn một hằng thời gian hay O 1 .Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là O max 1 1 O 1 Qui tắc nhân Nếu T1 n và T2 n là thời gian thực hiện của hai đoạn chương trình

• Tự động hoá
• giáo trình đại học
• tài liệu mạng
• giáo trình cơ điện
• giáo trình thiết kế
• tài liệu kế toán
• Chương trình giáo dục đại học
• Giáo trình giáo dục đại học
• Giáo dục đại học
• Tiểu luận giáo dục học
• Thuyết trình giáo dục đại học
• Giáo dục đại học Việt Nam
• Giáo dục đại học thế giới
• Suy nghĩ về giáo trình Đại học
• Xây dựng giáo trình Đại học
• Việc xây dựng giáo trình Đại học
• Chất lượng giáo trình Đại học
• Nâng cao chất lượng giáo trình Đại học
• Giáo dục đại học ngoài công lập
• Giảng viên đại học ngoài công lập
• Sinh viên đại học ngoài công lập
• Đánh giá chất lượng giáo dục đại học
• Chất lượng giáo dục đại học
• Giáo trình Quản lý giáo dục đại học quân sự
• Quản lý giáo dục đại học quân sự
• Kế hoạch quản lý giáo dục đại học quân sự
• Mục tiêu quản lý giáo dục đại học quân sự
• Quá trình quản lý giáo dục đại học quân sự
• Phương pháp quản lý giáo dục đại học quân sự
• Đại học ngoài công lập
• Quản lý giáo dục đại học ngoài công lập
• Giáo dục đại học ngoài công lập Việt Nam
• Đại học công lập
• Giáo dục đại học công lập
• Hệ thống giáo dục đại học Việt Nam
• Chất lượng sinh viên
• Cải cách giáo dục
• Giáo dục Hoa Kỳ
• Giáo dục đại học Hoa Kỳ
• Đặc điểm giáo dục đại học Hoa Kỳ
• Tài chính giáo dục
• Tài chính giáo dục đại học
• Tài chính giáo dục đại học Việt Nam
• Hệ mục tiêu trong chương trình giáo dục đại học
• Mục tiêu chương trình giáo dục đại học Việt Nam
• Mục tiêu chương trình đào tạo bậc đại học Hoa kỳ
• Hệ mục tiêu chung cho chương trình giáo dục đại học
• Thông tư số 07 2015 TT BGDĐT
• Trình độ đào tạo giáo dục đại học
• Quy trình xây dựng trình độ đại học
• Quy trình xây dựng trình độ thạc sĩ
• Quy trình xây dựng trình độ tiến sĩ
• Chuẩn đầu ra giáo dục đại học
• Thiết kế chương trình giáo dục đại học
• Mục tiêu giáo dục đại học
• Điều tra nhu cầu đào tạo
• Quy trình phát triển giáo dục đại học
• Giáo dục đại học Việt Nam và thế giới
• Đặc trưng giáo dục đại học
• Văn minh nông nghiệp
• Quản lý nhà trường đại học
• Quản lý giáo dục đại học
• Nghiên cứu khoa học trong giáo dục đại học
• Nghiên cứu khoa học
• Quản lý nguồn nhân lực giáo dục
• Quản lý nguồn nhân lực giáo dục đại học quân sự
• Quản lý cơ sở vật chất kỹ thuật giáo dục
• Quản lý chất lượng giáo dục đại học quân sự
• Giáo dục học đại cương
• Giáo trình giáo dục học đại cương 1
• Giáo dục học đại cương 1 phần 1
• Giáo dục học
• Giáo dục học là một khoa học
• Tâm lý giáo dục
• Đánh giá chất lượng giáo dục
• Chất lượng giáo dục
• Giáo dục ngoài công lập
• Giáo dục học đại cương 1 phần 2
• Giáo dục và sự phát triển nhân cách
• Giáo dục phổ thông Việt Nam
• Giáo dục phổ thông Phần Lan
• Giáo dục phổ thông
• Giáo dục Singapore
• Cấu trúc giáo dục Singapore
• Hệ thống giáo dục