Bài tập môn Phân tích thiết kế giải thuật | Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh

Xác định Big-O cho các đoạn chương trình sau: Bài 1: Bài 2: s=0; s = 1; p = 1; for (i= 1;i<=n;i++) for (i=1;i<=n;i++) s=s+i; { Bài 3: p = p * x / i; s = 0; s = s + p; for (i=0; i<=n;i++) } { Bài 4: p =1; for (i= 1;i<=n;i++) for (j=1;j<=i;j++) for (j= 1;j<=n;j++) p=p * x / j; cout≪i+j; s = s+p; Bài 6: } for (i= 1;i<=n;i++) Bài 5: { for (i= 1;i<=n;i++) for (u= 1;u<=m;u++) for (j= 1;j<=m;j++) for (v= 1;v<=n;v++) cout≪i*j; cout≪u+v; Bài 7: for (j= 1;j<=x;j++) for (i= 1;i<=n;i++) for (k= 1;k<=z;k++) for (j= 1;j<=m;j++) cout≪j*k; { } for (k= 1;k<=x;k++) Bài 8: cout≪k+j; int i=1; for (h= 1;h<=y;h++) while(i≤n) cout≪h+i; { } cout≪”Xin chao”; Bài 9: i=i*2; int i = 1; } while (i<= n) Bài 10: { for (i= 1;i<=n;i++) int j = 1; for (u= 1;u<= m;u++) while (j<=n) for (v= 1;v<=n;v++) { cout≪”Xin chao”; cout≪”Xin chao”; for (j= 1;j<=x;j++) j=j*3; for (k= 1;k<=z;k++) } cout≪”Các ban”; i=i+1; }
Bài 11: Giải các phương trình đệ quy: Bài 12:
T(n) = 2T(n-1) + C1 , T(1) = C2
Giải các phương trình đệ quy sau với T(1) = 1 𝑛
T(n) = T(n-1) + n, T(1) = 1, ∀𝑛 ≥ 2 T(n) = 4T( ) + n 2
𝑇(𝑛) = 𝑇 (𝑛) + 1, T(1) = 0, 𝑛 ∀𝑛 ≥ 2 2 T(n) = 4T( ) + n2 2
𝑇(𝑛) = 2𝑇 (𝑛) + 𝑛, T(1) = 0, 𝑛 ∀𝑛 ≥ 2 T(n) = 4T( ) + n3 2 2 𝑛 T(n) = 2T( ) + nlogn 2
Bài 13: Dãy Fibonacci được định nghĩa như sau: F0=1 F1=1 Fn=Fn-1 + Fn-2 (n>=2)
1. Cài đặt hàm tìm phần tử thứ n của dãy Fibonacci bằng 2 cách: a. Dùng đệ quy. b. Không dùng đệ quy.
2. Phân tích và đánh giá độ phức tạp thời gian của 2 hàm trên và lựa chọn cách nào.
3. Theo bạn còn cách cài đặt nào để độ phức tạp thời tối ưu hơn không? Nếu có thì trình bày cách đó.
Bài 14: Phân tích và đánh giá độ phức tạp thời gian của 2 hàm của thuật toán tìm kiếm nhị phân sau:
int binary_search(int a[],int n, int key) {
int mid, left = 0, right = n - 1; while (left<=right) { mid = (left + right) / 2; if (a[mid] == key) return mid; else if (a[mid] left = mid + 1; else right = mid - 1; } return -1; }
int binary_search_recursion(int a[], int left,int right, int key) { if (left > right) return -1; int mid = (left + right) / 2; if (a[mid] == key) return mid; if (a[mid] < key)
binary_search_recursion(a, mid + 1, right,key); else
binary_search_recursion(a, left, mid - 1,key); }