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


Đăng ký nhận thông báo về những video mới nhấ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===============

LongDT
« Prev
Next »
Copied !!!