Cần giúp đỡ về bài tập PT & TK giải thuật

Hieu_Nguyen · April 14, 2015, 2:09pm

Chào mọi người, mình mới học môn Phân tích và thiết kế giải thuật. Nói chung mình còn mơ hồ nhiều thứ lắm. Thầy cho mình một số bài tập, mặc dù đọc nhiều tài liệu về nó nhưng mình vẫn đang bí cách giải. Hay đúng hơn là mình chưa hiểu bản chất của lý thuyết này. Mọi người giúp mình với. Xin cảm ơn mọi người

For each of the following six functions, state its rate of growth using Θ notation; if possible,
use one of the Basic Asymptotic Efficiency Classes from Levitin Table 2.2. ExplaiAn your
reasoning in one line. Then sort the functions from lowest to highest order of growth.
a. 34n
b. n!
c. 2n+1
d. √(144 n)
e. (n – 4)!
f. 2 log2 n5
g. n4 / 200 + 100 n3 + 500000 - n

Itachi_Citus · April 14, 2015, 2:17pm

a. Θ(n)
b. Θ(n!)
c. Θ(n)
…
Giải thích thì dựa vào định nghĩa của big - theta để giải thích, chẳng hạn c1n <= 34n <= c2n với n >= 1 và c1=1, c2=35; đại khái vậy. Câu đầu tiên dễ, mấy câu sau cần cẩn thận lựa chọn c1, c2 và điểm bắt đầu của n.

Cái này là định nghĩa liên quan đến hàm số / dãy số của bên toán thôi, đừng cố gắng thắc mắc “tại sao lại có nó” mà những thứ liên quan đến khái niệm chỉ cần chấp nhận và hiểu cơ bản ý nghĩa là được rồi.