Cơ s
Cơ s
ở
ở
to
to
á
á
n h
n h
ọ
ọ
c
c
1. Cận trên, cận dưới:
• └X┘ Giá trị nguyên lớn nhất, nhỏ hơn hoặc
bằng X. Ví dụ: └2.5┘=2; └-7.3┘=-8
• ┌X┐ Giá trị nguyên nhỏ nhất, lớn hơn hoặc
bằng X. . Ví dụ: └2.5┘=3; └-7.3┘=-7
2. Logarithms: Giải thuật tăng chậm hơn sự tăng
N
• log
2
N = lgN; log
10
N = logN
• X>Y  log
B
X> log
B
Y

Y
=Y*log
B
X
• log
A
X= log
B
X/ log
B
A
3. Cây nhị phân:
• Khái niệm: Cây nhị phân là cây mà mỗi nút có
tối đa 2 cây con
Cơ s
Cơ s
ở
ở
to
to
á
á
n h
n h
ọ
ọ
c
c
• Bậc của cây:
- Cây nhị phân có N

to
á
á
n h
n h
ọ
ọ
c
c
4. Xác suất:
5. Phép tổng: Thường được tính trong vòng lặp
6. Sự tăng
của hàm số
Cơ s
Cơ s
ở
ở
to
to
á
á
n h
n h
ọ
ọ
c
c
7. Phân loại sự tăng:
• Omega lớn: g(x) thuộc Ω(f), g(n)>=cf(n), mọi
n>=n0

Thu
Thu
ậ
ậ
t to
t to
á
á
n chia đ
n chia đ
ể
ể
tr
tr
ị
ị
 Ví dụ: Tính n!
int factorial (int n)
{ if (n == 0) return 1;
else return n * factorial(n - 1);
}
 Tính tối ưu của giải thuật đệ qui?
int factorial (int n)
{ int c, fact = 1;
for (c = 1; c<= n; c++)
fact*= c;
return fact;
}
Thu
Thu

ờ
i chi
ế
m nhi
ề
u th
ờ
i gian h
ơ
n do
v
ừ
a ph
ả
i c
ấ
t và l
ấ
y các tr
ị
t
ừ ngăn xế
p,
v
ừ
a ph
ả
i th
ự
c hi

}
2. Tìm ước số chung lớn nhất của 2 số m, n. Ví dụ:
GCD(15,9)=3, GCD(51,34)=17
Duy
Duy
ệ
ệ
t cây đ
t cây đ
ệ
ệ
qui
qui
• Cây nhị phân với các thứ tự duyệt cây như sau:
Duyệt theo thứ tự trước (NLR)
Duyệt theo thứ tự giữa (LNR)
Duyệt theo thứ tựï sau (LRN).