Phân tích - Thiết kế thuật toán

[vothiensau]

Mình đang nghiên cứu về phần thuật toán và có 1 số thắc mắc mọi người giải đáp dùm nha.

1/Xem xét bài toán xác định xem 1 dãy số tùy ý n con số <x1, x2, ..., xn> có chứa các lần xuất hiện lặp lại của 1 con số nào đó hay không. Dẫn chứng rằng điều này có thể thực hiện theo thời gian theta(nlgn).

2/Làm sao để sửa đổi hầu hết mọi thuật toán để có 1 thời gian thực hiện tốt trong trường hợp tốt nhất?

[nguyen_lan2005]

Time là Đôla, là VNĐ... kakakakaka
==============
www.becivn.net
www.nguyenlan.net

[vothiensau]

trời ơi sao tự nhiên vô spam vậy pa ._.

[watch_midnight]

1.cho 2 vòng for{...} xet từng phần tử với toàn mảng , nếu có phần tử trùng thì thoát.
2. cau nay thì khong hiểu ý của bạn cho lắm.

[vothiensau]

nếu dùng 2 vòng for thì thời gian thực hiện sẽ là theta(n^2) chứ không phải theta(nlgn).

[Global]

1. Sử dụng 1 thuật toán sort nào đó có độ phức tạp là O(nlgn)
Quét xem có 2 thằng liên tiếp nào giống nhau không

2. Bài toán hơi khó hiểu ^^
Nhưng mình định nghĩa bài toán như vầy, không biết có hợp ý bạn không:
- Cho thuật toán T, ta định nghĩa một tập các thuật toán được sửa đổi từ T. Gọi là tập M(T), giả định M(T) hữu hạn.
- Vậy yêu cầu tìm phần tử m trong M(T) sao cho m chạy tốt nhất trong trường hợp tốt nhất của T. Điều này dễ dàng giải quyết bằng cách thử tất cả các trường hợp (vì giả định M(T) hữu hạn mà ^^)

Nếu bạn làm theo hướng này thì các công việc phải làm là:
a. Định nghĩa M(T) ứng với một thuật toán T cụ thể. Chẳng hạn thuật toán QuickSort thì M(T) có thể là 1 số biến thể của thuật toán QuickSort.
b. Định nghĩa trường hợp tốt nhất của T.Lưu ý nhá, không phải là trường hợp tốt nhất của m.
c. Tìm m thuộc M(T) tốt nhất, làm bằng thực nghiệm.

[nokokoro]

bạn cứ nghiên cứu tiếp đi nha

[victory11101]

cả nhà ai có tài liệu môn này post cho mình với
thank!

[ptaminh]

Mình đang nghiên cứu về phần thuật toán và có 1 số thắc mắc mọi người giải đáp dùm nha.

1/Xem xét bài toán xác định xem 1 dãy số tùy ý n con số <x1, x2, ..., xn> có chứa các lần xuất hiện lặp lại của 1 con số nào đó hay không. Dẫn chứng rằng điều này có thể thực hiện theo thời gian theta(nlgn).

2/Làm sao để sửa đổi hầu hết mọi thuật toán để có 1 thời gian thực hiện tốt trong trường hợp tốt nhất?

Ý tưởng của mình cho câu 1.

Dãy A = {X1,X2,... , Xn} là dãy cần kiểm tra
B = {}

    WHILE ( A != {} )       
       X = pop(A); // neu cai dat chi can tang chi so mang len 1
       if ( Add ( X, B ) == 0)
           return [có phần tử trùng trong A]
    return [các phần tử trong A đôi một khác nhau]

//    B là dãy có thư tự
//    Hàm X vô B cài đặt theo tư tưởng. 
//    X add vô không tạo thành nghịch thế
//    X add vô không được trùng
//    việc thêm 1 phần tử X vào B có chi phí không đáng kể ngoài trừ chi //    phí tìm kiếm.
//    Từ tiêu chí trên => B được cài đặt là cây nhị phân tìm kiếm

Về hàm add X vô B theo phân tích trên là việc thêm X vào một cây nhị phân tìm kiếm. Cái này không khó, thuật toán chắc mọi người biết rồi.

Chi phí như sau :

FOR i = 0 -> M
ChiPhi += log2(i);

Trường hợp xấu nhất phải duyệt đến cuối mới biết. => M = n
Trường hợp tốt nhất M = 1 Chi phi = 1.
trung bình M = N/2.

Nói chung chi phí này là 1 + log2(1) + log2(2) + ... + log2(n - 1) (n lần tính cả số 1)
và sẽ nhỏ hơn chi phí nlog2(n) = log2(n) + log2(n) + .... + log2(n) (n lần)

[heocondethuong19]

mình cũng đang rất cần tài liệu môn này nè.Đặc biệt là phân tích độ phức tạp thuật toán tìm khiếm nhị phân