Giải thuật và lập trình: Bài tập phần độ phức tạp giải thuật
Giải phóng thời gian, khai phóng năng lực
BÀI KIỂM TRA MÔN HỌC
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Ngày: 14/06/2019
Bài 1:
- Bạn hãy nêu ý nghĩa của việc phân tích thời gian thực hiện giải thuật
- Có bao nhiêu cách xác định đô phức tạp của giải thuật
Bài 2: Đối với việc xác định độ phức tạp của giải thuật theo quy tắc nhân:
Nếu đoạn chương trình P nào đó có thời gian thực hiện là T(n) = O(f(n)). Khi đó, nếu thực hiện k(n) lần đoạn chương trình P với k(n) = O(g(n)) thì độ phức tạp tính toán sẽ là:
O(g(n).f(n))
Bạn hãy chứng minh công thức xác định độ phức tạp tính toán trên là đúng.
Bài 3: Bạn hãy nêu quy luật tương đối khi tổ chức dữ liệu.
Bài 4: Cho thuật toán sắp xếp như sau:
int i, j, N;
N=100;
for(i=0; i<N; i++){
for(j=0; j<N; j++){
printf(“\n%d”,(i+j));
}
}
Bạn hãy xác định độ phức tạp của thuật toán trên bằng ký pháp chữ O.
Bài 5: Cho thuật toán sắp xếp như sau:
int i, j, N;
N=100;
for(i=0; i<N-1; i++){
for(j=i+1; j<N; j++){
printf(“\n%d”,(i+j));
}
}
Bạn hãy xác định độ phức tạp của thuật toán trên bằng ký pháp chữ O.
Bài 6: Cho thuật toán đệ quy sau:
int printNumber(int n){
printf("\n%d",n);
if(n==1){
return 1;
}else{
printNumber(n-1);
}
}
Bạn hãy xác định độ phức tạp của thuật toán trên bằng ký pháp chữ O.
Bài 7: Cho thuật toán cắt ký tự giữa chuỗi như sau:
void catDauCachGiuaChuoi(char str[]){
int i, j;
for(i=0; i<strlen(str)-1; i++){
while(str[i]==’ ‘ && str[i+1]==’ ‘){
for(j=i+1; j<strlen(str)-1; j++){
str[j] = str[j+1];
}
str[strlen(str)-1] = ’\0’;
}
}
printf(“\nSau khi cat dau cach thua giua chuoi, ta duoc: \”%s\””,str);
}
Bạn hãy xác định độ phức tạp của thuật toán trên bằng ký pháp chữ O.
===============HẾT===============
Giải phóng thời gian, khai phóng năng lực