Chương 1: Introduction - 10.Algorithms Analysis: Problems & Solutions(41-53)

Problem-41

Tìm độ phức tạp của hàm đệ quy: $T ( n ) = T ( \sqrt { n } ) + 1$
Solution: Áp dụng logic của Problem-40 ta được:
$S ( m ) = S ( \frac { m } { 2 } ) + 1$
Sử dụng master theorem ta có kết quả:
$S ( m ) = O ( l o g m )$
Thay m = logn trở lại ta được: $T ( n ) = S ( l o g n ) =O(loglogn)$

Problem-42

Tìm độ phức tạp của hàm đệ quy: $T ( n ) = 2T ( \sqrt { n } ) + 1$
Solution: Áp dụng logic của Problem-40 ta được:
$S ( m ) = 2S ( \frac { m } { 2 } ) + 1$
Sử dụng master theorem ta có kết quả:
$S ( m ) = O ( m ^ { l o g _ { 2 } ^ { 2 } } ) = 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 ( \sqrt { 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 (if n < 2)$
$= 8 T ( \frac { n } { 2 } ) + n ^ { 3 } + 1 (otherwise)$

Sử dụng master theorem ta có kết quả:
$T ( n ) = \Theta ( n ^ { lo g _ { 2 } ^ { 8 } } l o g n ) = \Theta ( n ^ { 3 } l o g n )$

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(n^2)$

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 ) = 2 T ( \frac { n } { 2 } ) + 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(log^2 n)$

Problem-50

$\Sigma _ { 1 \leq k \leq n } O ( n )$, trong đó O (n) là viết tắt của bậc n thì tổng trên có độ phức tạp:\

1. $O(n)$
2. $O(n^2)$
3. $O(n^3)$
4. $O(3n^2)$
5. $O(1.5n^2)$

Solution: (2) $\Sigma _ { 1 \leq k \leq n } O ( n ) = O ( n ) \Sigma _ { 1 \leq k \leq n } 1 = O ( n ^ { 2 } ) .$

Problem-51

Khẳng định nào sau đây là đúng
I) $\left ( n + k \right ) ^ { m } = \Theta ( n ^ { m } )$
II) $2 ^ { n + 1 } = O ( 2 ^ { n } )$
III) $2 ^ { 2n + 1 } = O ( 2 ^ { n } )$

1. I và II
2. I và III
3. II và III
4. Cả 3

Solution: (1) $( n + k ) ^ { m } = n ^ { k } + c 1 ^ { * } n ^ { k - 1 } + \ldots k ^ { m } = \Theta ( n ^ { k } )$
(2) $2 ^ { n + 1 } = 2 ^ { * } 2 ^ { n } = O ( 2 ^ { n } )$

Problem-52

Xem xét hàm sau: $f ( n ) = 2 ^ { n } \operatorname { g } ( n ) = n ! \operatorname { h } ( n ) = n ^ { l o g n }$
Phát biểu nào sau đây về tiệm cận của f(n), g(n), và h(n) là đúng\

1. $f(n) = O(g(n)); g(n) = O(h(n))$
2. $f(n) = Ω (g(n)); g(n) = O(h(n))$
3. $g(n) = O(f(n)); h(n) = O(f(n))$
4. $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à:\

1. $\operatorname { c e i l } ( l o g _ { 2 } ^ { n } ) { + } 1$
2. n
3. $\operatorname { c e i l } ( l o g _ { 2 } ^ { n } )$
4. $\operatorname { floor } ( l o g _ { 2 } ^ { n } ) { + } 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à $2^k$.
Lấy loga 2 vế ta được $k = l o g _ { 2 } ^ { n }$.
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)