Giải thuật và lập trình: Bài tập phần độ phức tạp giải thuật


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:

  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
  2. 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===============

« Prev
Next »