Chương 1: Tổng quát về cấu trúc dữ liệu và thuật toán

Chia sẻ: Nguyen Huy | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

78
lượt xem 15
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bât kỳ mot chương trình máy tính nào cũng cân có dữ liệu để xử lý.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 1: Tổng quát về cấu trúc dữ liệu và thuật toán

Chương 1 T NG QUAN V C U TRÚC D LI U & THU T TOÁN 1.1. Khái ni m v c u trúc d li u và thu t toán 1.1.1. C u trúc d li u 1.1.2. Thu t toán 1.1.3. S liên h gi a c u trúc d li u và thuât toán 1.2. Phân tích gi i thu t 1.2.1. Phân tích th i gian th c hi n gi i thu t 1.2.2. ð ph c t p tính toán c a gi i thu t 1.2.3. Xác ñ nh ñ ph c t p tính toán 1.3. Bài t p 1
1.1 Khái ni m v c u trúc d li u và thu t toán 1.1.1 C u trúc d li u B t kỳ m t chương trình máy tính nào cũng c n có d li u ñ x lý. D li u vào (input data), d li u trung gian x lý ho c d li u ra (output data). Do v y, vi c t ch c ñ lưu tr d li u cho chương trình có ý nghĩa r t quan tr ng, quy t ñ nh r t l n ñ n ch t lư ng cũng như công s c c a ngư i l p trình trong thi t k , cài ñ t chương trình… 2 2 Khoa CNTT Trư ng TC TÂY NAM Á © Dương Thành Ph t-www.thayphet.net
1.1.2 Gi i thu t Gi i thu t - Thu t gi i - Thu t toán dùng ñ ch phương pháp hay cách th c ñ gi i quy t v n ñ . Gi i thu t có th ñư c minh h a b ng ngôn ng t nhiên (natural language), b ng sơ ñ (flow chart) ho c b ng mã gi pseudo code). Trong th c t , gi i thu t thư ng ñư c minh h a b ng mã gi t a ngôn ng l p trình nào ñó như C, Pascal, … 3 3 Khoa CNTT Trư ng TC TÂY NAM Á © Dương Thành Ph t-www.thayphet.net
1.1.3 S liên h gi a c u trúc d li u và gi i thu t C u trúc d li u + Gi i thu t = Chương trình C u trúc d li u t t, n m v ng gi i thu t th c hi n thì vi c th hi n chương trình b ng m t ngôn ng c th ch là v n ñ th i gian. M t chương trình máy tính ch có th ñư c hoàn thi n khi có ñ y ñ c C u trúc d li u ñ lưu tr d li u và Gi i thu t x lý d li u theo yêu c u c a bài toán ñ t ra. 4 4 Khoa CNTT Trư ng TC TÂY NAM Á © Dương Thành Ph t-www.thayphet.net
1.2. Phân tích gi i thu t 1.2.1 Các tiêu chu n ñánh giá c u trúc d li u Ph i ti t ki m tài nguyên (b nh trong), Ph i ph n nh ñúng th c t c a bài toán, Ph i d dàng trong vi c thao tác d li u.. 5 5 Khoa CNTT Trư ng TC TÂY NAM Á © Dương Thành Ph t-www.thayphet.net
1.2.2 ðánh giá ñ ph c t p c a thu t toán ðánh giá ñ ph c t p c a m t thu t toán là ư c lư ng th i gian th c hi n thu n toán T(n) ñ so sánh tương ñ i gi a các thu t toán. Th i gian th c hi n m t thu t toán còn ph thu c r t nhi u ñi u ki n khác như: c u t o máy tính, d li u ñưa vào, …, ta ch xét trên m c ñ c a lư ng d li u ñưa vào ñ ư c lư ng th i gian th c hi n: Trong trư ng h p t t nh t: Tmin Trong trư ng h p x u nh t: Tmax Và ư c lư ng th i gian trung bình Tavg 6 6 Khoa CNTT Trư ng TC TÂY NAM Á © Dương Thành Ph t-www.thayphet.net
1.2.3 Phân tích thu t toán B ng các c p th i gian th c hi n thu t toán ñư c s d ng r ng rãi. Ký hi u ô l n Tên g i thông thư ng O(1) H ng O(log2n) logarit O(n) Tuy n tính O(nlog2n) nlog2n O(n2) Bình phương O(n3) L p phương O(2n) Mũ 7 7 Khoa CNTT Trư ng TC TÂY NAM Á © Dương Thành Ph t-www.thayphet.net
Ví d : Tìm trong dãy s a1, a2,..., an m t ph n t có giá tr b ng x. Vào: Dãy s nguyên a[N] và khoá c n tìm x Ra: V trí ph n t có khoá x ho c là -1 n u không tìm th y. Int Timtuyentinh (int a[] , int N , int x) { int i; i = 0; while((i < N) && (a[i] != x)) i=i+1; if( i == N) return -1 ; // h t m ng không có x else return i ; //a[i] là ph n t có khóa x. } 8 8 Khoa CNTT Trư ng TC TÂY NAM Á © Dương Thành Ph t-www.thayphet.net
N u a[0] = x thì l nh i := i + 1 trong vòng l p th c hi n 1l n. Do ñó th i gian tính t t nh t c a thu t toán là O(1). N u x không có trong dãy thì l nh i := i + 1ñư c th c hi n n l n. Vì th th i gian tính x u nh t là O(n). Th i gian tính trung bình c a thu t toán. N u x ñư c tìm th y v trí th i thì l nh i := i + 1 th c hi n i l n (i = 1, 2, ..., n), N u x không xu t hi n trong dãy thì l nh i := i + 1 th c hi n n l n. [(1 + 2 + ... + n) + n] /(n + 1) 9 9 Khoa CNTT Trư ng TC TÂY NAM Á © Dương Thành Ph t-www.thayphet.net
Ta có: [(1 + 2 + ... + n) + n] /(n + 1) ≤ (n2 + n)/(n + 1) = n V y th i gian tính trung bình c a thu t toán là O(n). 10 10 Khoa CNTT Trư ng TC TÂY NAM Á © Dương Thành Ph t-www.thayphet.net