Cơ sở cấu trúc dữ liệu và thuật toán
Mục lục- Cơ sở cấu trúc dữ liệu và thuật toán
- Khoa học máy tính là gì?
- Cách hiểu trực quan về thuật toán và ý nghĩa
- Phân tích thuật toán là gì?
- Tiêu chí đánh giá chương trình
- Độ phức tạp thời gian biểu thức Big O T(n)=O(f(n))
- Cấu trúc dữ liệu
- Phân tích hiệu năng cấu trúc dữ liệu trong Python
Khoa học máy tính là gì?
Cần nhận thức rõ rằng khoa học máy tính không đơn thuần là nghiên cứu về máy tính, dù công cụ này đóng vai trò quan trọng trong phát triển khoa học.
Thực chất đây là lĩnh vực nghiên cứu cách giải quyết vấn đề và tìm kiếm giải pháp tối ưu cho các bài toán. Ví dụ khi gặp bài toán cụ thể, nhà khoa học máy tính sẽ xây dựng thuật toán để xử lý, từ đó tìm ra kết quả hoặc nghiệm tối ưu. Vì vậy có thể xem khoa học máy tính chính là nghiên cứu về các thuật toán. Từ đó thấy được thuật toán là tư duy, phương pháp để giải quyết vấn đề.
Cách hiểu trực quan về thuật toán và ý nghĩa
# Hiểu biết
Một vị tướng thiện chiến luôn lên kế hoạch chiến lược trước trận đấu, nhằm đạt chiến thắng nhanh nhất với chi phí thấp nhất.
Nếu xem lập trình là chiến trường thì lập trình viên chính là người chỉ huy. Làm sao để chương trình của bạn chạy nhanh nhất và tiết kiệm tài nguyên nhất? Thuật toán chính là chiến lược!
# Ý nghĩa
Tư tưởng cấu trúc dữ liệu và thuật toán có tính ứng dụng rộng rãi, được sử dụng xuyên suốt trong mọi ngôn ngữ lập trình. Đây là hai kỹ năng nền tảng mà lập trình viên chuyên nghiệp cần trau dồi.
Tư duy về cấu trúc dữ liệu và thuật toán giúp mở rộng khả năng lập trình, giúp bạn thấu hiểu sâu sắc hơn bản chất của lập trình.
Phân tích thuật toán là gì?
Sinh viên mới học lập trình thường so sánh chương trình mình viết với người khác. Dù hai chương trình giải cùng bài toán nhưng lại có sự khác biệt.
Ví dụ bài toán: Tìm các bộ số nguyên (x,y,z) thỏa mãn x+y+z=1000 và x²+y²=z²
# Giải pháp 1
import datetime
start_time = datetime.datetime.now()
for x in range(0,1001):
for y in range(0,1001):
for z in range(0,1001):
if x+y+z == 1000 and x**2 + y**2 == z**2:
print(x,y,z)
end_time = datetime.datetime.now()
print (end_time - start_time)
# Kết quả: Chạy hơn 4 phút
0 500 500
200 375 425
375 200 425
500 0 500
0:04:15.526003
# Giải pháp 2
import datetime
start_time = datetime.datetime.now()
for x in range(0,1001):
for y in range(0,1001):
z = 1000 - x - y
if x+y+z == 1000 and x**2 + y**2 == z**2:
print(x,y,z)
end_time = datetime.datetime.now()
print (end_time - start_time)
# Kết quả: Chạy xong trong 2 giây
0 500 500
200 375 425
375 200 425
500 0 500
0:00:02.117703
Tiêu chí đánh giá chương trình
- Tiêu thụ tài nguyên hệ thống và tốc độ thực thi (khó quan sát trực tiếp, phụ thuộc vào phần cứng)
- Đo lường thời gian thực thi (không nên dùng do phụ thuộc môi trường, nên dùng thời gian trung bình)
- Độ phức tạp thời gian (nên dùng)
Độ phức tạp thời gian biểu thức Big O T(n)=O(f(n))
- Quy tắc đánh giá: Đếm số thao tác cơ bản hoặc bước thực hiện
- Yếu tố quan trọng: Thuật ngữ có ảnh hưởng lớn nhất trong biểu thức
- Sử dụng ký pháp Big O
O(n) (n là yếu tố quan trọng nhất)Bỏ qua hệ số 2n --> nBỏ qua hạng tử bậc thấp n²+n --> n²Thông thường nói đến trường hợp xấu nhất- Độ phức tạp càng thấp thì thuật toán càng tốt
- Một số độ phức tạp phổ biến:
- O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)
# Ví dụ độ phức tạp
def tongN(n):
ket_qua = 0 # 1
for i in range(1,n+1): # n+1
ket_qua += i
return ket_qua
print(tongN(10))
# 1+n+1 ==> O(n)
a=5 # 1
b=6 # 1
c=10 # 1
for i in range(m):
for j in range(m): # 3m²
x = i * i
y = j * j
z = i * j
for k in range(m): # 2m
w = a*k + 45
v = b*b
d = 33 # 1
# 3+3m²+2m+1 ==>m²==>O(m²)
Cấu trúc dữ liệu
- Khái niệm: Cách tổ chức dữ liệu (kiểu dữ liệu cơ bản như số nguyên, số thực, ký tự) được gọi là cấu trúc dữ liệu. Cấu trúc dữ liệu giải quyết cách lưu trữ nhóm dữ liệu và hình thức lưu trữ như thế nào. (Trong Python, tất cả kiểu dữ liệu cơ bản đều là object)
- Ví dụ: Lưu trữ thông tin sinh viên (tên, điểm), nên tổ chức như thế nào? Độ phức tạp truy vấn là bao nhiêu? (Ba cách tổ chức)
# Cách 1 Độ phức tạp O(n)
[{
'ten':'abc',
'diem':'xyz'
},{
'ten':'def',
'diem':'ghi'
},{
'ten':'jkl',
'diem':'mno'
}]
# Cách 2 Độ phức tạp O(n)
[
('ten','diem'),
('ten','diem'),
('ten','diem')
]
# Cách 3 Độ phức tạp O(1)
{
'nguyen_van_a':{'diem':'xyz'},
'tran_van_b':{'diem':'ghi'}
}
# Mối quan hệ cấu trúc dữ liệu và thuật toán?
- Tổ chức dữ liệu theo các hình thức khác nhau sẽ có độ phức tạp truy vấn khác nhau. Vì vậy thuật toán là công cụ giải quyết vấn đề, còn cấu trúc dữ liệu là nền tảng để thuật toán hoạt động.
Phân tích hiệu năng cấu trúc dữ liệu trong Python
Thêm phần tử vào danh sách là thao tác lập trình phổ biến. Có hai cách thường dùng là append và phép nối (+). Nhưng cách nào hiệu quả hơn?
- Module timeit: Công cụ đo tốc độ thực thi đoạn mã Python.
- Lớp Timer: Được dùng để đo thời gian thực thi mã trong timeit. Cú pháp: class timeit.Timer(stmt='pass',setup='pass').
- stmt: Đoạn mã cần kiểm tra.
- setup: Thiết lập ban đầu cho đoạn mã.
- timeit(number=100000): Trả về thời gian trung bình sau number lần thực thi.
- Tạo danh sách rỗng và thêm 0-m phần tử. (Bốn phương pháp)
from timeit import Timer
def test1():
ds = []
for i in range(1000):
ds += [i]
return ds
def test2():
ds = []
for i in range(1000):
ds.append(i)
return ds
def test3():
return [i for i in range(1000)]
def test4():
ds = list(range(1000))
return ds
if __name__ == '__main__':
t1 = Timer('test1()','from __main__ import test1').timeit(100000)
print(t1)
t2 = Timer('test2()','from __main__ import test2').timeit(100000)
print(t2)
t3 = Timer('test3()','from __main__ import test3').timeit(100000)
print(t3)
t4 = Timer('test4()','from __main__ import test4').timeit(100000)
print(t4)
# Kết quả: Phương pháp 4 nhanh nhất là list(range(1000))
11.752772499999992
10.816332999999986
11.822587399999975
9.485878500000013