TAILIEUCHUNG - Giáo trình phân tích quy trình ứng 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 quy trình ứng 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ệ, điện - điện tử 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

Khánh Minh 75 5 pdf

Upload

Bấm vào đây để xem trước nội dung

Tải xuống

TÀI LIỆU LIÊN QUAN

Tiểu luận: Tình hình chung của giáo dục đại học, giáo dục đại học ngoài công lập. Hãy phân tích về: Chương trình – Giáo trình

32 730 15

Mấy suy nghĩ về giáo trình Đại học

7 283 0

Thuyết trình giáo dục đại học: Tình hình chung của giáo dục đại học tại Việt Nam và giáo dục đại học ngoài công lập đề cập đến giảng viên và sinh viên

21 272 3

Thuyết trình giáo dục đại học: Đánh giá chất lượng giáo dục đại học

43 328 4

Giáo trình Quản lý giáo dục đại học quân sự: Phần 1

72 3 1

Thuyết trình giáo dục đại học: Thực trạng tổ chức, quản lý giáo dục đại học ngoài công lập tại Việt Nam

17 268 0

Thuyết trình giáo dục đại học: Tình hình chung của giáo dục đại học Việt Nam

20 277 7

Thuyết trình giáo dục đại học: Vấn đề dạy và học trong giáo dục đại học nói chung và ngoài công lập nói riêng

29 242 0

Tiểu luận: Tình hình chung của giáo dục đại học, giáo dục đại học công lập

30 277 2

Tiểu luận: Tình hình chung của giáo dục đại học, giáo dục đại học ngoài công lập. Hãy phân tích: Tổ chức, quản lý?

40 243 0

TÀI LIỆU XEM NHIỀU

Một Case Về Hematology (1)

8 461848 55

Giới thiệu :Lập trình mã nguồn mở

14 22528 57

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 10867 529

Câu hỏi và đáp án bài tập tình huống Quản trị học

14 10030 445

Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”

3 9491 104

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8245 1124

Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức

16 8207 423

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 7860 2220

Đề tài: Dự án kinh doanh thời trang quần áo nữ

17 6648 253

Vật lý hạt cơ bản (1)

29 5756 85

TỪ KHÓA LIÊN QUAN

TÀI LIỆU MỚI ĐĂNG

Oreilly learning the vi Editor phần 4

19 228 0 20-04-2024

Magnetic Bearings Theory and Applications phần 2

14 170 0 20-04-2024

MÔN HỌC VẬT LIỆU VÀ CÔNG NGHỆ KIM LOẠI - PHẦN I: KIM LOẠI HỌC

32 175 2 20-04-2024

Đề tài: Tìm hiểu một số yêu cầu đặt ra với một phòng thu âm, để đảm bảo chất lượng âm thanh trong sản phẩm đa phương tiện

8 158 1 20-04-2024

HƯỚNG DẪN SỬ DỤNG PHẦN MỀM CAITA part 9

18 126 0 20-04-2024

Giáo trình tổng quan khoa học thông tin và thư viện part 7

22 143 2 20-04-2024

New Trends and Developments in Automotive Industry Part 7

35 91 0 20-04-2024

Bài Tiểu Luận Chuyên Đề Tổ Chức Hoạt Động Nhận Thức Trong Dạy Học Vật Lý " Định Luật Ôm Cho Các Loại Đoạn Mạch Chứa Nguồn Điện"

10 150 3 20-04-2024

Lãi suất cơ bản, công cụ quan trọng của chính sách tiền tệ

5 111 0 20-04-2024

Giáo trình kỹ thuật sữa chữa ô tô, máy nổ part 8

47 136 1 20-04-2024

TÀI LIỆU HOT

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 7860 2220

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 5609 1332

Ebook Chào con ba mẹ đã sẵn sàng

112 3752 1229

Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1

62 5256 1127

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8245 1124

Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu

561 3474 641

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 10867 529

Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân

122 3670 524

Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm

274 4026 513

Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe

35 4105 478