30/09/2018, 18:30
Làm thế nào để tính được độ phức tạp của thuật toán?
chào các anh(chị,bạn)
em đang học môn cấu trúc dữ liệu và giải thuật
e đang mắc chỗ làm thế nào để tính độ phức tạp của thuật toán
e đã đọc tài liệu
công thức max, quy tắc nhân, bỏ hằng số,…vv e hiểu
cách tìm cũng đã hiểu
nhưng e chưa biết cách tính độ phức tạp của 1 thuật toán (đã code) cụ thể
nghĩa là việc xác định số phép tính sơ cấp, khi nào dung quy tắc max, nhân e chưa rõ
1 số bài toán dài dòng thì chưa tính được
cách tính độ phức tạp trong vòng lặp while, for, do while , đệ quy…
mong giúp đỡ
Bài liên quan
Có dòng code rồi chưa chắc đã tính dc dpt của thuật toán:
vd:
function sort(a,n)
repeat i=random()%n; j=random()%n; swap(a[i],a[j]);
Until is-sorted(a)
End
:3 mình đang hỏi chỗ cách tính độ phức tạp của thuật toán ấy, mình chứ bị ngờ ngợ giữa các quy tắc
Ngoài các quy tắc cơ bản cộng nhân, hằng số thì có 1 số thuật toán có độ phức tạp rất khó, mà phải các chuyên gia đánh giá (ví dụ dijkstra, quicksort,…) những cái này thì bạn nhớ. Còn các quy tắc cơ bản thì cứ dùng bt đánh giá thôi
đếm số vòng for. 1 số thuật toán độ phức tạp ramdom
Làm thế nào tối ưu code nhỉ? Mình có thể code được nhưng thuật toán và đoạn code của mình nó sao sao hình như là không tối ưu vẫn đến tốc độ xử lý của chương trình chậm. Ở đây mình không nói đến thuật toán mà mình chỉ hỏi là làm sao để tối ưu code. Cụ thể là mình không biết được code mới nó có tối ưu hơn code cũ không, Và làm thế nào để mình biết cách sửa code cũ lại cho nó tối ưu hơn
Đếm số vòng for? bạn có qua môn DSA chưa đó?
chưa bạn ơi mình mới học môn CTDL & GT, mà chưa thấy cô nói gì đến độ phức tạp của thực toán, chỉ dạy toàn các cấu trúc dữ liệu. Lúc trước có học Toán rời rạc nên cũng biết sơ sơ, biết được số phép gán, so sánh trong 1 chương trình đơn giản. Cái mình cần là làm sao để biết khi nào cần dùng cái này khi nào cần dùng cái kia để tối ưu, ví dụ như khi cần lưu trữ 1 biến có giá trị nhỏ thì dùng kiểu
char, short,..., biến có giá trị lớn thì dùngdouble, long,..