TAILIEUCHUNG - Giáo trình cấu trúc dữ liệu và giải thuât part 2

Tham khảo tài liệu 'giáo trình cấu trúc dữ liệu và giải thuât part 2', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | fỉ. Thông thường thời gian thực hiên giải thuật vần dược chú ý hơn. Vì vậy sau dây ta sẽ xét tới việc đánh giá thời gian thực hiện giải thuật . Thời gian thực hiện một giải thuật chịu ảnh hưởng của nhiổu yếu tố. Như ta đã biết các kiểu lệnh và thời gian thực hiện các lệnh của các loại máy tính thường khác nhau. Hơn nữa ngôn ngữ lập trình và chất lượng của chương trình dịch cũng là các yếu tố liên quan tới thời gian thực hiện giải thuật. Vì vây ta không thể tính thời gian này bang phút bang giây. như cách đo thời gian thông thường để rồi so sánh với nhau. Cùng một giải thuật nhưng thực hiện trên hai loại máy khác nhau với ngôn ngữ lập trình và chương trình dịch khác nhau sẽ đưa tới chi phí về thời gian lính theo phút theo giây. khác nhau. Vậy thì dựa vào đâu để có thể nói rằng giải thuật này nhanh hơn giải thuật kia Trước hết ta thấy Thời gian thực hiện giải thuật thường phụ thuộc vào kích thước của bộ dữ liệu nói gọn là kích thước dữ liệu . Ví dụ Sắp xếp một dãy n sổ thì kích thước dữ liệu là n n càng lớn thì thời gian sắp xếp càng lâu. Do đó người ta tìm cách biểu diễn thời gian thực hiện giải thuật bằng một hàm só của kích thước n T n việc xác định kích thước của dữ liệu tuỳ thuộc vào từng bài toán cụ thể . Rõ ràng là T n độc lập với các yếu tố khách quan đã nêu ỏ trên. Với cách tiếp cận này cùng một bài toán nếu giải thuật A có thời gian thực hiện là Tị n - 8n và một giải thuật A2 có thời gian thực hiện là T2 n 2n2 thì khi n đủ lớn ta thấy Tj n T2 n ở dãy chỉ cần n 4 là 2n2 8n và n càng lớn thì sự chênh lệch càng rõ. Như vậy lúc đó ta có thể nói Khi n đủ lớn thì giải thuật A nhanh hơn giải thuật A2. Trong thực tố với tốc độ tính toán của MTĐT như hiện nay thì việc so sánh thời gian thực hiện giải thuật chỉ đặt ra khi n khá lớn thôi lúc đó độ chênh lệch mới đáng kể . Vấn đề đặt ra bây giờ là Làm thế nào dể xác định được T n - Trước hết ta hãy xét một ví dụ Giải thuật tính giá trị trung bình của n số Program TB các số ở đây được coi như n giá trị khác nhau cùa X

• Cơ sở dữ liệu
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• phân tích thiết kế
• thiết kế hướng đối tượng
• Data Structures and Algorithms