Cấu trúc dữ liệu - Chương 2: Các kiểu dữ liệu cơ bản

1Các kiểu dữ liệu cơ bản Chương 2 Kiểu tập tin4 Kiểu mảng và chuỗi1 Kiểu cấu trúc2 Kiểu con trỏ3 Độ phức tạp thuật toán5 Nội dung 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu chuỗi (String)  Một chuỗi là dãy liên tiếp các ký tự kết thúc bằng ký tự \0 có mã ASCII bằng 0 (NULL character)  Trong C chuỗi có tối đa 65535 ký tự  Các hàm xử lý chuỗi được đặt trong thư viện string.h của C. Các cấu trúc lưu trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu chuỗi (String) Khai báo chuỗi: có thể dùng các cách sau  char S[10]; //Khai báo một chuỗi ký tự S có chiều dài // tối đa 10 (kể cả kí tự kết thúc)  char S[]="ABC";// Khai báo một chuỗi ký tự S có chiều // dài bằng chiều dài của chuỗi "ABC" // và giá trị khởi đầu của S là "ABC"  char *S ="ABC";//Giống cách khai báo trên. Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu chuỗi (String) Một số thao tác trên chuỗi Các kiểu dữ liệu có cấu trúc  So sánh 2 chuỗi: strcmp  Sao chép chuỗi: strcpy  Độ dài chuỗi: strlen  Kiểm tra 1 chuỗi nằm trong chuỗi kia: strstr  Cắt 1 từ ra khỏi 1 chuỗi: strtok  Đổi 1 số ra chuỗi: itoa  Đổi 1 chuỗi ra số: atoi, atof, ...  Nhập một chuỗi: gets  Xuất một chuỗi: puts Các cấu trúc ư trữ trên bộ nhớ chính 23/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu mảng (Array)  Mảng là một tập hợp các biến có cùng tên và kiểu dữ liệu, được lưu trữ liên tiếp trong bộ nhớ  Mỗi phần tử được đánh chỉ số (Index), phần tử đầu tiên có chỉ số là 0  Trong C, một mảng n chiều có thể coi là mảng 1 chiều trong đó mỗi phần tử là 1 mảng n-1 chiều. Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu mảng (Array): Khai báo mảng [][]...; Ví dụ, ta có thể khai báo:  Float a[10]; //khai báo mảng 1 chiều có 10 phần tử  int a[100][150];//khai báo mảng 2 chiều  int a[][]={{1, 7, -3, 8, 19},{4, 5, 2, 8, 9},{21, -7, 45, -3, 4}}; Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu hợp (Union)  Union là một kiểu dữ liệu đặc biệt trong C, nó tương tự kiểu struct nhưng các phần tử lại dùng chung một vùng nhớ  Cách thức truy xuất đến các thành phần trong kiểu Union giống như kiểu cấu trúc  Dùng kiểu Union khi cần lưu trữ dữ liệu thay đổi theo trạng thái Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu hợp (Union): Khai báo kiểu union typedef union { ; ; ……… }[]; Các kiểu dữ liệu có cấu trúc Ví dụ, ta có thể định nghĩa kiểu số sau: typedef union tagNumber { int i; long l; }Number; Number N; Khi gán N.l=0xFF09 thì thành phần N.i sẽ nhận giá trị là 9 Các cấu trúc ư trữ trên bộ nhớ chính 33/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu cấu trúc (Structure)  Kiểu cấu trúc (hay kiểu mẫu tin) là một tập hợp các biến khác tên và có thể khác nhau về kiểu dữ liệu  Cách thức truy xuất đến các thành phần trong kiểu cấu trúc: Têncấutrúc.Tênthànhphần  Dùng kiểu cấu trúc khi muốn lưu trữ thông tin của các đối tượng phức tạp và đa dạng Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu cấu trúc (Structure): Khai báo kiểu cấu trúc typedef struct { ; ; ……… }[]; Các kiểu dữ liệu có cấu trúc Ví dụ, ta có thể định nghĩa kiểu cấu trúc ngày tháng như sau: typedef struct { int ngay; int thang; int nam; }Ngaythang; Ngaythang N;//khai báo biến Các cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu cấu trúc (Structure): Truy xuất dữ liệu Các kiểu dữ liệu có cấu trúc  Cách thức truy xuất đến các thành phần trong kiểu cấu trúc: Têncấutrúc.Tênthànhphần  Để lấy địa chỉ của một thành phần trong cấu trúc, ta dùng toán tử &: &Têncấutrúc.Tênthànhphần Vd: Ngaythang N,M; printf(“Nhập ngày tháng: ”); scanf(“%d/%d/%d”,&N.ngay,&N.thang,&N.nam); M=N;//gán biến cấu trúc N vào biến M Các cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu cấu trúc (Structure): Hàm và kiểu cấu trúc Các kiểu dữ liệu có cấu trúc  Đối của hàm có thể là: - Biến mẫu tin: khi đó tham số thực tương ứng là một giá trị mẫu tin - Tham chiếu mẫu tin: khi đó tham số thực tương ứng là một địa chỉ mẫu tin - Con trỏ mẫu tin: khi đó tham số thực là địa chỉ của biến cấu trúc.  Hàm có thể trả về: - Giá trị mẫu tin: Ngaythang tênhàm(...) - Con trỏ mẫu tin: Ngaythang *tênhàm(....) Các cấu trúc ư trữ trên bộ nhớ chính 43/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu con trỏ (Pointer)  Kiểu con trỏ là một kiểu dữ liệu đặc biệt trong C, có kích thước 2 bytes và dùng để chứa địa chỉ của một biến đã được cấp phát bộ nhớ  Khi biến con trỏ chứa địa chỉ của biến A ta nói nó đang trỏ tới biến (vùng nhớ) A  Nếu con trỏ chứa giá trị NULL nghĩa là nó không trỏ đến vùng nhớ nào hết Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu con trỏ (Pointer) Khai báo biến con trỏ  Trực tiếp: *; Vd: int *P,*Q;//khai báo biến  Gián tiếp: typedef *; ; Vd: typedef int *intPointer;//khai báo kiểu intPointer P,Q;//khai báo biến Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu con trỏ (Pointer) Khai báo biến con trỏ  Con trỏ void: con trỏ được khai báo kiểu void có thể chứa địa chỉ của bất kỳ kiểu nào. Tuy nhiên trước khi sử dụng phải ép về một kiểu cụ thể Vd: int X; float Y; void *P; P=&X; //P trỏ đến X (float*) P=&Y; //P trỏ đến Y (int*) P=&X; //P trỏ đến X Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu con trỏ (Pointer) Các thao tác  Gán địa chỉ một biến cho con trỏ tênbiếncontrỏ = &tênbiếncầnlấyđịachỉ; tênbiếncontrỏ = NULL; Ví dụ:  Chứa địa chỉ của mảng 1 chiều: int *P , A[10]; --> P = A;  Chứa địa chỉ của mảng 2 chiều: float *P, B[3][4]; --> P = (float*) B;  Chứa địa chỉ của 1 biến cấu trúc: struct HocSinh *P, hs; --> P = &hs; Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 53/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu con trỏ (Pointer) Các thao tác  Truy xuất nội dung 1 biến do biến con trỏ trỏ đến Cú pháp:*tênbiếncontrỏ Lưu ý: toán tử * và & có cùng độ ưu tiên Ví dụ: int X, *P; X=10; P=&X; //P trỏ đến X printf(“Giá trị X là: %d”,X); printf(“Giá trị do P trỏ đến: %d”,*P); Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu con trỏ (Pointer) Các phép toán  So sánh địa chỉ chứa trong hai con trỏ, dùng toán tử == hoặc !=  Khi sử dụng con trỏ trên mảng, ta có thể thực hiện các phép toán sau  Cộng địa chỉ con trỏ: pt + i ==>Cộng địa chỉ vùng nhớ lưu trong pt với i*sizeof(T)  Trừ hai con trỏ: pt1-pt2 ==>số phần tử có kích thước sizeof(T) giữa 2 địa chỉ. Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu con trỏ (Pointer) Con trỏ và mảng 1 chiều  Tên mảng là hằng địa chỉ của phần tử đầu tiên trong mảng, có thể thực hiện phép cộng địa chỉ với tên mảng. Khi đó (A+i) tương ứng với &A[i]  Ta cũng có thể sử dụng con trỏ trên mảng với các phép toán sau  Lấy địa chỉ phần tử thứ i : &A[i]  Cộng địa chỉ Vd: int i, *p, A[3]={10,20,30}; p=A;// hoặc p=&A[0]; for (i=0;i<3;i++) printf(“A[%d]=%d”,i,*(A+i)); for (i=0;i<3;i++) printf(“A[%d]=%d”,i,*(p+i)); Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu con trỏ (Pointer) Con trỏ và mảng 2 chiều  Tên mảng là hằng địa chỉ của phần tử đầu tiên trong mảng, có thể thực hiện phép cộng địa chỉ với tên mảng. Khi đó (A+i) tương ứng với &A[i][0] Vd: float A[3][2]; ta có A ứng với &A[0][0]; (A+1) ứng với &A[1][0]; (A+2) ứng với &A[2][0]  Ta cũng có thể sử dụng con trỏ trên mảng với các phép toán sau  Lấy địa chỉ phần tử A[i][j] : p+i*sốcột+j  Cộng địa chỉ Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 63/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu con trỏ (Pointer) Con trỏ và mảng 2 chiều Vd: int i,j,k; float *p, A[3][3]; p=(float*)A;// hoặc p=(float*)&A[0][0]; for (i=0;i<3;i++) //In theo mảng 2 chiều for (j=0;j<3;j++) printf(“A[%d][%d]=%d”,i,j,*(p+i*3+j)); for (k=0;k<3*3;k++) //In theo mảng 1 chiều printf(“A[%d]=%d”,k,*(p+k)); Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu con trỏ (Pointer) Con trỏ và kiểu cấu trúc  Lấy địa chỉ của một phần tử trong cấu trúc ta dùng toán tử & Vd :struct Ngay{ int ngay,thang,nam;}X; struct Ngay *p; p=&X; //p trỏ đến cấu trúc X  Để truy xuất giá trị của pt trong cấu trúc ta có thể  Cách 1: *(p).ngay, *(p).thang, *(p).nam  Cách 2: pngay, pthang, pnam Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu con trỏ (Pointer) Con trỏ hàm  Là con trỏ dùng để chứa địa chỉ của hàm  Khai báo hàm và con trỏ hàm phải trung khớp với nhau về các đối số và kiểu dữ liệu trả về  Trước khi dùng phải gán tên hàm cho con trỏ hàm Vd : int Hoanvi( int *x, int *y); //khai báo hàm int (*p)( int*, int*)=Hoanvi; //khai báo con trỏ hàm int x=2, y=3; Hoanvi(&x, &y); //dùng tên hàm p(&x, &y); //dùng con trỏ hàm Các kiểu dữ liệu có cấu trúcCác cấu trúc ư trữ trên bộ nhớ chính 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu tập tin (File)  Ưu điểm của RAM: truy xuất nhanh  Nhược điểm của RAM: kích thước hạn chế, không lưu trữ thông tin khi mất điện  Giải pháp: lưu trữ trên bộ nhớ ngoài (ổ đĩa)  Ưu: kích thước lớn, lưu trữ lâu dài  Nhược: truy xuất chậm do sử dụng thiết bị cơ khí Các kiểu dữ liệu có cấu trúcấu trúc lưu trữ trên bộ nhớ ngoài 73/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu tập tin (File)  Có 2 loại tập tin  Tập tin văn bản (Text file)  Tập tin nhị phân (Binary file)  Các bước làm việc với tập tin 1. Khai báo biến tập tin 2. Mở tập tin 3. Truy xuất nội dung tập tin 4. Đóng tập tin  Trong C, các hàm xử lý tập tin có trong thư viện stdio.h Các kiểu dữ liệu có cấu trúcấu trúc lưu trữ trên bộ nhớ ngoài 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu tập tin (File) Các bước thao tác trên tập tin 1. Khai báo biến tập tin: FILE *ContrỏFile;  File được kết thúc bởi ký tự có mã 26 (EOF) 2. Mở tập tin: ContrỏFile = fopen (char *têntậptin, char *kiểu); Cấu trúc lưu trữ trên bộ nhớ ngoài Mở file để đọc ghi. Nếu file cũ thì nối thêm,nếu không thì tạo mới“a+” Mở file để ghi thêm vào cuối file“a” Mở file mới đọc hoặc ghi.“w+” Mở file mới để ghi. Nếu file đã có sẽ bị xóa“w” Mở để sửa“r+” Mở để đọc. Nếu không có File sẽ báo lỗi“r” Mở tập tin kiểu văn bản“t” Mở tập tin kiểu nhị phân“b” Ý nghiãKiểu 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu tập tin (File) Các bước thao tác trên tập tin Ví dụ: FILE *fp; fp = fopen(“C:\\DSHS.DBF”, “wb”); if ( fp == 0 ) { perror(“Loi Mo File:”); exit(1); } Các kiểu dữ liệu có cấu trúcấu trúc lưu trữ trên bộ nhớ ngoài 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu tập tin (File) Các bước thao tác trên tập tin 3. Truy xuất dữ liệu file văn bản  File văn bản: đặc điểm ký tự xuống hàng gồm CR(13) và LF(10), khi đọc CR + LF  trả về ký tự “\n”, khi ghi ký tự “\n”  CR + LF  Đọc ghi dữ liệu tuần tự  Ghi dữ liệu • int putc ( int ch, FILE *fp); • int fputc (int ch, FILE *fp); • int fputs (const char *Str, FILE *fp); • int fprintf (FILE *fp, const char *dk, các biểu thức); Cấu trúc lưu trữ trên bộ nhớ ngoài 83/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu tập tin (File) Các bước thao tác trên tập tin 3. Truy xuất dữ liệu file văn bản  Đọc dữ liệu • int getc (FILE *fp) ; • int fgetc (FILE *fp) ; • char *fgets (char * Str, int n, FILE *fp); • int fscanf (FILE *fp, const char *dk, địa chỉ các biến); Cấu trúc lưu trữ trên bộ nhớ ngoài 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu tập tin (File) Các bước thao tác trên tập tin 3. Truy xuất dữ liệu file nhị phân  File nhị phân: không có ký tự xuống dòng, mỗi lần đọc ghi theo một khối byte (Record)  Đọc ghi dữ liệu tại vị trí Record bất kỳ  Ghi các Record vào File: int fwrite(void *ptr, int sizeofItem, int n, FILE *fp);  Đọc các Record trên File: int fread (void *ptr, int sizeofItem, int n, FILE *fp); Cấu trúc lưu trữ trên bộ nhớ ngoài 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu tập tin (File) Các bước thao tác trên tập tin 3. Truy xuất dữ liệu file nhị phân  Kiểm tra cuối file: int feof (FILE *fp);  Vị trí con trỏ byte: long ftell (FILE *fp);  Di chuyển đầu đọc File: void rewind (FILE *fp); int fseek (FILE *fp, long sốbyte, int vịtríxuấtphát);  Đánh dấu vị trí đầu đọc ghi: int fgetpos (FILE *fp, fpos_t *vịtrí); Cấu trúc lưu trữ trên bộ nhớ ngoài 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu tập tin (File) Các bước thao tác trên tập tin 3. Truy xuất dữ liệu file nhị phân  Quay lại vị trí đã đánh dấu: int fsetpos(FILE * fp, fpos_t *vịtrí);  Đổi tên / di chuyển file : int rename (const char *OldFile, const char *NewFile);  Xóa tập tin: int remove (const char * path); Cấu trúc lưu trữ trên bộ nhớ ngoài 93/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu tập tin (File) Các bước thao tác trên tập tin 4. Đóng tập tin  int fclose (FILE *fp); Nếu có lỗi hàm cho EOF ngược lại cho giá trị 0.  int fcloseall ( ); Nếu có lỗi cho EOF nếu không cho số file được đóng. Cấu trúc lưu trữ trên bộ nhớ ngoài 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu tập tin (File) Các ví dụ int main(int n, char * a[]) //n là số đối số trên dòng lệnh kể cả //tên chương trình a[0] { FILE *fp; char c; int sobyte=0; if (n != 2) { puts("Loi cu phap: "); exit(1); } fp = fopen(a[1], "wt"); while (( c = getchar()) != EOF) //hàm getchar() trả về EOF { putc( c, fp); sobyte++; } //khi có lỗi hoặc ấn F6 printf("\n\t 1 file copy \t\t %d bytes ", sobyte); fclose(fp); } Cấu trúc lưu trữ trên bộ nhớ ngoài 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu tập tin (File) Các ví dụ int main(int n, char * a[]) { FILE *fp; char st[80]; int sobyte=0; if (n != 2) { puts("Loi cu phap: "); exit(1); } fp = fopen(a[1], "wt"); while ( gets(st)) != NULL) //hàm gets(st) trả về NULL khi có lỗi { fputs( st, fp); fputs("\n", fp); //hoặc ấn F6 sobyte+=strlen(st); } printf("\n\t 1 file copy \t\t %d bytes ", sobyte); fclose(fp); } Cấu trúc lưu trữ trên bộ nhớ ngoài 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Kiểu tập tin (File) Các ví dụ typedef struct pointtype Polygol[10]; Polygol P; void main(void) { FILE *fp; char c; int n,i; fp = fopen("c:\\dagiac.dat","rt"); fscanf(fp,"%d",&n); printf("%d\n",n); for (i=0; i<n; i++) fscanf(fp,"%d %d",&P[i].x,&P[i].y); fclose(fp); } Cấu trúc lưu trữ trên bộ nhớ ngoài 10 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Thời gian thực hiện của thuật toán  Là số lệnh cần thiết mà máy tính thực hiện khi chạy chương trình sử dụng thuật toán  Thời gian thực hiện một chương trình là một hàm không âm của kích thước dữ liệu vào, ký hiệu T(n), T(n) 0 n0  Thông thường chỉ quan tâm đến thời gian thực hiện trong trường hợp xấu nhất Đánh giá độ phức tạp thuật toán 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Tỷ lệ tăng của hàm (Growth Rate)  Cho hai hàm không âm T1(n) và T2(n)  T1(n) có tỷ lệ gia tăng giống như T2(n) nếu tồn tại các hằng số c và n0 : T1(n) ≤ c.T2(n) với mọi n ≥ 1 Ví dụ: Tìm tỷ lệ gia tăng của hàm T1(n) =(n+1)2 Ta thấy T1(n) =n2+2n+1 ≤ n2+2n2+n2=4n2 với mọi n ≥ 1  chọn c=4, n0=1 , ta nói T1(n) =(n+1)2 có tỷ lệ tăng như T2(n) =n2 Đánh giá độ phức tạp thuật toán 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Độ phức tạp của thuật toán (Complexity)  Cho hai hàm T1(n) và T2(n)  T1(n) có độ phức tạp là T2(n) nếu tồn tại các hằng số c và n0 : T1(n) ≤ c.T2(n) với mọi n ≥ n0  Ký hiệu: T1(n) = O(T2(n)) đọc là “ô của T2(n)”  Thông thường T2(n) là dạng hàm đã biết như: log2n, n, nlog2n, n2, n3, 2n, n!, nn ... Đánh giá độ phức tạp thuật toán 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Độ phức tạp của thuật toán (Complexity) Đánh giá độ phức tạp thuật toán O(1) n T(n) 11 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Cách tính độ phức tạp của thuật toán (Complexity)  Qui tắc nhân:  Cho hai đoạn chương trình P1và P2 lồng nhau; T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của đoạn hai đoạn chương trình đó là T(n) = O(f(n).g(n))  Qui tắc cộng:  Cho hai đoạn chương trình P1 và P2 nối tiếp nhau; 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 đó là T(n)=O(max(f(n),g(n))) Đánh giá độ phức tạp thuật toán 3/11/2010 www.lhu.edu.vn Chương 2 Các kiểu dữ liệu cơ bản Cách tính độ phức tạp của thuật toán (Complexity) void BubleSort(int a[], int N ) { int i, j, tepm; {1} for (i = 0 ; i<N-1 ; i++) {2} for (j =N-1; j >i ; j --) {3} if(a[j]< a[j-1]) // nếu sai vị trí thì đổi chỗ {4} { temp = a[j]; {5} a[j] = a[j-1]; {6} a[j-1] = temp; } }  độ phức tạp là O(n2) Đánh giá độ phức tạp thuật toán