TAILIEUCHUNG - Giáo trình giải thuật của Nguyễn Văn Linh part 2

Nếu chúng ta có một chương trình với các chương trình con không đệ quy, để tính thời gian thực hiện của chương trình, trước hết chúng ta tính thời gian thực hiện của các chương trình con không gọi các chương trình con khác. Sau đó chúng ta tính thời gian thực hiện của các chương trình con chỉ gọi các chương trình con mà thời gian thực hiện của chúng đã được tính. Chúng ta tiếp tục quá trình đánh giá thời gian thực hiện của mỗi chương trình con sau khi thời gian thực hiện của tất. | Giải thuật Kĩ thuật phân tích giải thuật - Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng qui tắc cộng. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh. - Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là O 1 . - Thời gian thực hiện vòng lặp là tổng trên tất cả các lần lặp thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp. Ví dụ 1-7 Tính thời gian thực hiện của thủ tục sắp xếp nổi bọt PROCEDURE Bubble VAR a ARRAY OF integer VAR i j temp Integer BEGIN 1 FOR i 1 TO n-1 DO 2 FOR j n DOWNTO i 1 DO 3 IF a j-1 a j THEN BEGIN hoán vị a i a j 4 temp a j-1 5 a j-1 a j 6 a j temp END END về giải thuật sắp xếp nổi bọt chúng ta sẽ bàn kĩ hơn trong chương 2. Ở đây chúng ta chỉ quan tâm đến độ phức tạp của giải thuật. Ta thấy toàn bộ chương trình chỉ gồm một lệnh lặp 1 lồng trong lệnh 1 là lệnh 2 lồng trong lệnh 2 là lệnh 3 và lồng trong lệnh 3 là 3 lệnh nối tiếp nhau 4 5 và 6 . Chúng ta sẽ tiến hành tính độ phức tạp theo thứ tự từ trong ra. Trước hết cả ba lệnh gán 4 5 và 6 đều tốn O 1 thời gian việc so sánh a j-1 a j cũng tốn O 1 thời gian do đó lệnh 3 tốn O 1 thời gian. Vòng lặp 2 thực hiện n-i lần mỗi lần O 1 do đó vòng lặp 2 tốn O n-i .1 O n-i . Vòng lặp 1 lặp có I chạy từ 1 đến n-1nên thời gian thực hiện của vòng lặp 1 và cũng là độ phức tạp của giải thuật là T n g n - i Jfcl O n2 . Chú ý Trong trường hợp vòng lặp không xác định được số lần lặp thì chúng ta phải lấy số lần lặp trong trường hợp xấu nhất. Ví dụ 1-8 Tìm kiếm tuần tự. Hàm tìm kiếm Search nhận vào một mảng a có n số nguyên và một số nguyên x hàm sẽ trả về giá trị logic TRUE nếu tồn tại một phần tử a i x ngược lại hàm trả về FALSE. Nguyễn Văn Linh Trang 5 Sưu tầm bởi Giải thuật Kĩ thuật phân .

• Kỹ thuật lập trình
• Kỹ thuật lập trình
• giải thuật
• hướng dẫn giải thuật
• cấu trúc dữ liệu
• lập trình
• kỹ thuật máy tính C
• kỹ thuật lập trình C
• giáo trình kỹ thuật lập trình C
• bài tập kỹ thuật lập trình C
• tài liệu kỹ thuật lập trình C
• chuyên ngành kỹ thuật lập trình
• Bài tập kỹ thuật lập trình
• Tài liệu kỹ thuật lập trình
• Bài giảng kỹ thuật lập trình
• Ưng dụng kỹ thuật lập trình
• Ngôn ngữ C
• kỹ thuật máy tính
• môn kỹ thuật lập trình
• ôn tập kỹ thuật lập trình
• cách học kỹ thuật lập trình
• kiến thức kỹ thuật lập trình
• học môn kỹ thuật lập trình
• Đề thi Kỹ thuật lập trình cơ bản
• Câu hỏi Kỹ thuật lập trình cơ bản
• Luyện thi Kỹ thuật lập trình cơ bản
• Ôn thi Kỹ thuật lập trình cơ bản
• Bài thi Kỹ thuật lập trình cơ bản
• Tài liệu Kỹ thuật lập trình cơ bản
• giáo trình kỹ thuật lập trình
• thủ thuật lập trình
• lập trình căn bản
• kỹ thuật phần mềm
• chương trình lập trình
• giáo trình lập trình
• lập trình hướng đối tượng
• tài liệu lập trình
• chuyên ngành lập trình
• tổng quan về lập trình
• Tổng quan về kỹ thuật lập trình
• Lập trình tốt
• Nguyên tắc lập trình
• Ngôn ngữ lập trình
• ngôn ngữ C++
• Kỹ thuật lập trình căn bản
• Kỹ thuật lập trình nâng cao
• Lập trình C căn bản
• Lập trình C nâng cao