Mình đang đoc về tìm dãy con chung dài nhất của 2 chuổi. X,Y độ dài m,n
Ở đoạn thuật toán trực tiếp như sau:
Bước 1: duyệt tất cả các dãy con có thể của X (2m)
Bước 2: Với mỗi xâu con của X kiếm tra xem có trong Y hay không (O(n)) - đoạn này mình chưa hiểu
ĐỘ phức tạp : (n*2m)
Ai giải thích giúp mình với.
Đây là link mình đoc: http://faculty.cs.tamu.edu/klappi/csce411-f17/csce411-set6b.pdf
Đoạn:
Giả sử dãy A ngắn hơn dãy B (nếu bằng nhau thì so sánh bt). Vậy để trả lời câu hỏi thì nếu gặp một phần tử nào của A trong B thì ta ghi nhận và tiến tới phần tử tiếp theo của A. Nếu B hết phần tử trước thì không phải và ngược lại.
Trong trường hợp xấu nhất số lần đọc là theta(m+n). Tốt nhất thì vẫn là theta(m).
Vì nói là trực tiếp nên mình cứ nghĩ so sánh theo kiểu: liệt kê tất cả các xâu con của 2 dãy X,Y: sau đó với mỗi xâu con của X sẽ tìm xem có trong Y hay không thì phải là 0(2mũ (m+n)). Để viết toán học trên đây xem ở đâu vậy bạn.
Cám ơn bạn.
Không đúng, nếu cứ so sánh theo cách bình thường thì sẽ cần O(n^2) phép so sánh nếu m = cn và sắp xếp theo những cách đặc biệt. Cách sắp xếp rất tuỳ ý nên không thể cố định bước nhảy.
Bài này phải dùng hashing, counting gì đó chứ không phải cứ nói O(n) đơn giản được luôn đâu.
có vẽ như bạn chưa hiểu bài toán.
Tập con khác dãy con 
dãy con có thứ tự “sequence”
LCS thì phải đi thẳng vào cách giải dynamic programming chứ nhỉ? Bài toán kinh điển mà 
mình biết, nhưng mình muốn hiểu cái giải tuật tuần tự nó như nào thôi.
Ví dụ dãy gốc: nnnnnnxnnnnnnnnxnnnnnnnnn (6n/1x/8n/1x/9n)
Substring: nnnnxnnnnnnnnn (4n/1x/9n) Thì cần bao nhiêu phép so sánh?
Bài toán nhân lên với substring lớn, dãy gốc lớn (asymptotically large - lớn vô tận) và thêm nhiều cách sắp xếp ký tự tương tự nhưng không đoán được quy luật, ví dụ: nnnnnnxnnnnnnnnn(6n/1x/9n). Phương pháp bình thường bắt buộc phải chạy từng phần tử giống phần tử đầu, duyệt tệ nhất m - c’ lần mỗi phần tử. Chắc chắn sẽ cần O(n^2) phép so sánh với n = cm, c là hằng số.
dãy con khác chuỗi con đó bạn.
chẳng hạn như X = A B C D E F G
Z = C C E D E G F
thì dãy con chung dài nhất: là C D E G
câu hỏi là tại sao tìm vị trí của chuỗi A có độ dài a trong chuỗi B có độ dài b có time complexity O(b) mà, sao đi trả lời tìm LCS ko vậy :V
Vì nó là một bước trong thuật toán trực tiếp nên mình hỏi vậy, nếu có ai cũng đang đọc phần này mà chưa rõ thì cũng dễ theo dõi hơn.
Nếu nói định nghĩa sequence X được tạo từ set S và x1 != x2 != x3… != xn thì mình công nhận và cũng chẳng có gì cần nói thêm cho bài này nữa. Nhưng cái dãy mà bạn đưa ra, bản chất nó khác chuỗi ở chỗ nào vậy?? Đừng nói với mình là cặp ngoặc kép nhé.
như mình hiểu thì dãy thì không cần phải liên tục:
ví dụ:
ABC có dãy con là: rỗng, A,B,C, AB, AC,AC, ABC *
nhưng chuỗi con thì có: rỗng, A, B, C, AB, BC, ABC **
ở bài này là dũng cái trường hợp *
In mathematic, a sequence is an enumerated collection of objects in which repetitions are allowed.
Một sequence có 2 thuộc tính:
Vậy cái chuỗi mà mình đưa ra nó vi phạm điều nào vậy?
Chính xác, thì 1 string là 1 sequence of characters, được cấu thành từ tập ký tự và nó chính là 1 sequence nhé!
không vi phạm điều nào cả, chỉ khác ở chỗ kiểm tra xem nó có là dãy con của 1 chuỗi không thôi, tồi nhất là 0(n+m) như bạn gì ở trên kia có nói đấy.
Wiki cũng thống kê luôn cái naive search đó độ phức tạp O(nm), nếu n = cm thì chả là O(n^2), how could it be O(n + m), magic? :v
Nếu không tin cứ viết code của giải thuật naive, 1 là running time O(nm), hai là bị lỗi “bỏ sót” với trường hợp đặc biệt như ở trên.
Check O(n) được nhé. Dùng “2 con trỏ”.
// check t có là dãy con của s hay không
i = 0
j = 0
for i = 0 -> len(s) - 1:
if t[j] == s[i]:
j++
return j == len(t)
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?