Chapter 2: Các kiểu dữ liệu cơ bản

Chia sẻ: Thanh Tran | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

96
lượt xem 4
download

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

Kiểu chuỗi (String) Kiể chuỗ 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 dữ lưu trữ cấu trúcnhớ chính Cáccấể trúữ liệu tró trên trú nhớ chí kiể trd c liệ có ú bộ ki cữ bộ

Chủ đề:

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

Lưu

Nội dung Text: Chapter 2: Các kiểu dữ liệu cơ bản

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