Problem-41
Tìm độ phức tạp của hàm đệ quy: T(n)=T(n)+1
Solution: Áp dụng logic của Problem-40 ta được:
S(m)=S(2m)+1
Sử dụng master theorem ta có kết quả:
S(m)=O(logm)
Thay m = logn trở lại ta được: T(n)=S(logn)=O(loglogn)
Problem-42
Tìm độ phức tạp của hàm đệ quy: T(n)=2T(n)+1
Solution: Áp dụng logic của Problem-40 ta được:
S(m)=2S(2m)+1
Sử dụng master theorem ta có kết quả:
S(m)=O(mlog22)=O(m)
Thay m = logn trở lại ta được: T(n)=O(logn)
Problem-43
Tìm độ phức tạp của hàm đệ quy:
public static int function(int n){
if(n <= 2) return 1;
else return (function((int) Math.floor(Math.sqrt(n))) + 1);
}
Solution: Xem xét comments
public static int function(int n){
if(n <= 2) return 1; //constant time
else return (function((int) Math.floor(Math.sqrt(n))) + 1); //execute sqrt(n) + 1 lần
}
Ta có thể xác định T(n) như sau:
T(n)=T(n)+1
Bài toán này giống Problem 41
Problem-44
Tìm độ phức tạp của hàm đệ quy:
static int counter;
public static void function(int n){
if(n < 2) return;
else counter = 0;
for (int i = 1; i <= 8; i++) {
function(n/2);
}
for (int i = 1; i <= Math.pow(n, 3); i++) {
counter++;
}
}
Solution: Xem xét comments
static int counter;
public static void function(int n){
if(n < 2) return; //constant time
else counter = 0;
//Vòng lặp thực thi 8 lần với giá trị của n giảm 1 nửa mỗi lần gọi
for (int i = 1; i <= 8; i++) {
function(n/2);
}
//Vòng lặp này thực thi n^3 lần với thời gian mỗi vòng lặp là không đổi
for (int i = 1; i <= Math.pow(n, 3); i++) {
counter++;
}
}
Ta có thể xác định T(n) như sau:
T(n)=1(ifn<2)
=8T(2n)+n3+1(otherwise)
Sử dụng master theorem ta có kết quả:
T(n)=Θ(nlog28logn)=Θ(n3logn)
Problem-45
Tìm độ phức tạp của đoạn pseudocode sau:
temp = 1
repeat
for i = 1 to n
temp = temp + 1;
n = n/2;
until n <= 1
Solution: Xem xét comments
temp = 1 //constatnt time
repeat
//Vòng lặp này thực thi n lần
for i = 1 to n
temp = temp + 1;
//Tiếp tục vòng lặp với giá trị n giảm 1 nửa
n = n/2;
until n <= 1
Ta có thể xác định T(n) như sau:
T(n)=T(n/2)+n
Sử dụng master theorem ta có kết quả:
T(n)=O(n)
Problem-46
Tìm độ phức tạp:
public void function(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j = j*2) {
System.out.println("*");
}
}
}
Solution: Xem xét comments
public void function(int n) {
//Vòng lặp này thực thi n lần
for (int i = 1; i < n; i++) {
//Vòng lặp này thực thi log(n) lần
for (int j = 1; j < n; j = j*2) {
System.out.println("*");
}
}
}
=> Độ phức tạp của chương trình O(nlogn)
Problem-47
Tìm độ phức tạp:
public void function(int n) {
for (int i = 1; i < n/3; i++) {
for (int j = 1; j < n; j = j + 4) {
System.out.println("*");
}
}
}
Solution: Xem xét comments
public void function(int n) {
//Vòng lặp này thực thi n/3 lần
for (int i = 1; i < n/3; i++) {
//Vòng lặp này thực thi n/4 lần
for (int j = 1; j < n; j = j + 4) {
System.out.println("*");
}
}
}
=> Độ phức tạp của chương trình O(n2)
Problem-48
Tìm độ phức tạp:
public void function(int n) {
if(n <= 1) return;
if(n > 1){
System.out.println("*");
function(n/2);
function(n/2);
}
}
Solution: Xem xét comments
public void function(int n) {
if(n <= 1) return; //constatnt time
if(n > 1){
System.out.println("*"); //constant time
function(n/2); //Gọi lại hàm với giá trị n giảm 1 nửa
function(n/2); //Gọi lại hàm với giá trị n giảm 1 nửa
}
}
Ta có thể xác định T(n) như sau:
T(n)=2T(2n)+1
Sử dụng master theorem ta có kết quả:
T(n)=O(n)
Problem-49
Tìm độ phức tạp:
public void function(int n) {
int i = 1;
while (i < n) {
int j = n;
while (j > 0)
j = j / 2;
i = 2 * i;
}
}
Solution: Xem xét comments
public void function(int n) {
int i = 1;
while (i < n) {
int j = n;
while (j > 0)
j = j / 2; //logn lần
i = 2 * i; //logn lần
}
}
=> Độ phức tạp của chương trình O(logn∗logn)=O(log2n)
Problem-50
Σ1≤k≤nO(n), trong đó O (n) là viết tắt của bậc n thì tổng trên có độ phức tạp:\
-
O(n)
-
O(n2)
-
O(n3)
-
O(3n2)
-
O(1.5n2)
Solution: (2) Σ1≤k≤nO(n)=O(n)Σ1≤k≤n1=O(n2).
Problem-51
Khẳng định nào sau đây là đúng
I) (n+k)m=Θ(nm)
II) 2n+1=O(2n)
III) 22n+1=O(2n)
-
I và II
-
I và III
-
II và III
-
Cả 3
Solution: (1) (n+k)m=nk+c1∗nk−1+…km=Θ(nk)
(2) 2n+1=2∗2n=O(2n)
Problem-52
Xem xét hàm sau: f(n)=2ng(n)=n!h(n)=nlogn
Phát biểu nào sau đây về tiệm cận của f(n), g(n), và h(n) là đúng\
-
f(n)=O(g(n));g(n)=O(h(n))
-
f(n)=Ω(g(n));g(n)=O(h(n))
-
g(n)=O(f(n));h(n)=O(f(n))
-
h(n)=O(f(n));g(n)=Ω(f(n))
Solution: (4) Theo tốc độ tăng trưởng: h(n)<f(n)<g(n) (g(n) tiệm cận đứng lớn hơn f(n) và f (n) tiệm cận đứng lớn hơn h(n)).
Ta có thể dễ dàng nhận thấy thứ tự trên bằng cách lấy logarit của 3 hàm đã cho: lognlogn<n<log(n!). Lưu ý rằng: log(n!)=O(nlogn)
Problem-53
int j=1, n;
while(j <= n)
j=j*2;
Số phép so sánh được thực hiện khi thực hiện vòng lặp cho n> 0 bất kỳ là:\
-
ceil(log2n)+1
-
n
-
ceil(log2n)
-
floor(log2n)+1
Solution: Giả sử rằng vòng lặp thực hiện k lần. Sau bước thứ k, giá trị của j là 2k.
Lấy loga 2 vế ta được k=log2n.
Vì chúng ta đang thực hiện một so sánh nữa cho việc thoát khỏi vòng lặp => đáp án (1)