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(n)+1T ( n ) = T ( sqrt { n } ) + 1T(n)=T(n​)+1Solution: Áp dụng logic của Problem-40 ta được: S(m)=S(m2)+1S ( m ) = S ( frac { m } { 2 } ) + 1S(m)=S(2m​)+1 Sử dụng master theorem ta có kết quả:S(m)=O(logm)S

Đã đăng trên bởi aithietke

Problem-41

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

Sử dụng master theorem ta có kết quả:
T(n)=Θ(nlog28logn)=Θ(n3logn)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)+nT(n) = T(n/2) + n

Sử dụng master theorem ta có kết quả:
T(n)=O(n)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)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)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)=2T(n2)+1T ( n ) = 2 T ( frac { n } { 2 } ) + 1
Sử dụng master theorem ta có kết quả:
T(n)=O(n)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)O(logn * logn) = O(log^2 n)

Problem-50

Σ1≤k≤nO(n)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)O(n)
  2. O(n2)O(n^2)
  3. O(n3)O(n^3)
  4. O(3n2)O(3n^2)
  5. O(1.5n2)O(1.5n^2)

Solution: (2) Σ1≤k≤nO(n)=O(n)Σ1≤k≤n1=O(n2).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) (n+k)m=Θ(nm)left ( n + k right ) ^ { m } = Theta ( n ^ { m } )
II) 2n+1=O(2n)2 ^ { n + 1 } = O ( 2 ^ { n } )
III) 22n+1=O(2n)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=nk+c1∗nk−1+…km=Θ(nk)( n + k ) ^ { m } = n ^ { k } + c 1 ^ { * } n ^ { k – 1 } + ldots k ^ { m } = Theta ( n ^ { k } )
(2) 2n+1=2∗2n=O(2n)2 ^ { n + 1 } = 2 ^ { * } 2 ^ { n } = O ( 2 ^ { n } )

Problem-52

Xem xét hàm sau: f(n)=2ng⁡(n)=n!h⁡(n)=nlognf ( 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))f(n) = O(g(n)); g(n) = O(h(n))
  2. f(n)=Ω(g(n));g(n)=O(h(n))f(n) = Ω (g(n)); g(n) = O(h(n))
  3. g(n)=O(f(n));h(n)=O(f(n))g(n) = O(f(n)); h(n) = O(f(n))
  4. h(n)=O(f(n));g(n)=Ω(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)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!)lognlogn < n < log(n!). Lưu ý rằng: log(n!)=O(nlogn)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. ceil⁡(log2n)+1operatorname { c e i l } ( l o g _ { 2 } ^ { n } ) { + } 1
  2. n
  3. ceil⁡(log2n)operatorname { c e i l } ( l o g _ { 2 } ^ { n } )
  4. floor⁡(log2n)+1operatorname { 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à 2k2^k.
Lấy loga 2 vế ta được k=log2nk = 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)

Nguồn: viblo.asia

Bài viết liên quan

Check nameservers của tên miền xem website trỏ đúng chưa

Tìm hiểu cách check nameservers của tên miền để xác định tên miền đó đang dùn

Mình đang dùng Google Domains để check tên miền hàng ngày

Từ khi thông báo dịch vụ Google Domains bỏ mác Beta, mình mới để ý và bắt đầ

Cách sử dụng SFTP (Giao thức truyền file qua SSH an toàn hơn)

SFTP là cách an toàn để truyền files giữa các máy tính, gữa máy local và web hostin

Hotlinking: Key Reasons to Avoid and Methods to Protect Your Site

Hotlinking might seem an easy way to acquire website assets, but in reality, it brings several disad