- vừa được xem lúc

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

0 0 17

Người đăng: Đặng An

Theo Viblo Asia

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(lognlogn)=O(log2n)O(logn * logn) = O(log^2 n)

Problem-50

Σ1knO(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) Σ1knO(n)=O(n)Σ1kn1=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+c1nk1+km=Θ(nk)( n + k ) ^ { m } = n ^ { k } + c 1 ^ { * } n ^ { k - 1 } + \ldots k ^ { m } = \Theta ( n ^ { k } )
(2) 2n+1=22n=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)+1\operatorname { 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)+1\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à 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)

Bình luận

Bài viết tương tự

- vừa được xem lúc

Đôi chút về cấu trúc dữ liệu và thuật toán

Theo anh Phạm Huy Hoàng (toidicodedao) đã viết trong blog của mình là kiến thức trong ngành IT có 2 loại, một là càng để lâu thì càng cũ, lạc hậu và trở lên vô dụng. Hai là càng để lâu thì càng có giá trị thậm chí ngày càng có giá.

0 0 42

- vừa được xem lúc

Cấu trúc dữ liệu Merkle Tree

Cây Merkle là một cây nhị phân có thứ tự được xây dựng từ một dãy các đối tượng dữ liệu (d1, d2,...,dn) sử dụng hàm băm h. Các “lá” của cây là các giá trị băm h(di) đối với 1 ≤ i ≤ n.

0 0 64

- vừa được xem lúc

Cách xây dựng cấu trúc dữ liệu Stack và Queue.

Mở đầu. Hello các bạn, hôm nay mình sẽ chia sẻ với các bạn cách để có thể tự xây dựng 2 loại cấu trúc dữ liệu stack(ngăn xếp) và queue(hàng đợi) sử dụng mảng trong C++;.

0 0 43

- vừa được xem lúc

Tối ưu ứng dụng với cấu trúc dữ liệu cơ bản

Ở Việt Nam có một nghịch lý ai cũng biết: hầu hết sinh viên ngành CNTT đều đã học cấu trúc dữ liệu và giải thuật, thuộc các môn bắt buộc. Thế nhưng lại rất hiếm khi ứng dụng vào công việc hoặc bị loại

0 0 48

- vừa được xem lúc

Chương 1: Introduction - Analysis of Algorithrms

Trong bài viết này mình sẽ nói về cách chúng ta sẽ sử dụng để phân tích và so sánh các loại thuật toán khác nhau. 1.

0 0 26

- vừa được xem lúc

Chương 1: Introduction - Các khái niệm cơ bản

Lời nói đầu. Trước khi có máy tính, đã có các thuật toán.

0 0 24