Bảng tra thuật ngữ
Bảng tra thuật ngữ
Bạn đang đọc một bài nào đó trong sách và vấp phải một từ mà bài trước đã định nghĩa. Trang này để tra trong mười giây rồi quay lại chỗ đang đọc, chứ không phải để đọc từ đầu tới cuối.
Mỗi mục ở đây gồm bốn thứ: tên tiếng Việt, tên tiếng Anh đúng như nó xuất hiện trong sách giáo khoa và trong tài liệu thư viện, một câu định nghĩa, và đường dẫn tới bài dạy thuật ngữ đó. Định nghĩa cố ý ngắn. Nếu một câu chưa đủ thì bạn cần bài dạy chứ không cần một câu dài hơn, và nút liên kết nằm ngay dưới mỗi thẻ.
Ô tìm kiếm quét đồng thời tên tiếng Việt, tên tiếng Anh và cả nội dung định nghĩa. Nhờ vậy gõ utf-8 ra được mục Ký tự và byte trong tiếng Việt dù chữ đó chỉ nằm trong phần định nghĩa, và gõ pivot ra Chốt. Bộ lọc chương thu hẹp về đúng một chương, hai nút sắp xếp đổi giữa thứ tự chữ cái và thứ tự chương, núm Bỏ dấu quyết định hai phía có được gỡ dấu trước khi so hay không, còn nút Xoá bộ lọc trả cả bốn thứ đó về mặc định cùng lúc. Con số bên phải thanh công cụ luôn là số thẻ thật đang hiển thị: bảng không có phân trang nên không có chuyện danh sách bị cắt bớt phía sau.
- Bậc tăngGrowth rateC1 · Đo chi phí
Tốc độ chi phí lớn lên khi dữ liệu vào lớn lên. Nó xếp giải thuật thành hằng, log, tuyến tính, n log n, bậc hai và luỹ thừa.
Mở bài dạy thuật ngữ này - Bài con gối nhauOverlapping subproblemsC8 · Quy hoạch động
Điều kiện thứ nhất để quy hoạch động có lãi: cùng một bài con phải xuất hiện lại nhiều lần trong cây gọi.
Mở bài dạy thuật ngữ này - Băm cuộnRolling hashC9 · Chuỗi
Tính mã băm của cửa sổ kế tiếp từ mã băm cửa sổ hiện tại trong thời gian hằng số: trừ ký tự đi ra, nhân cơ số, cộng ký tự đi vào, tất cả theo modulo.
Mở bài dạy thuật ngữ này - Băm lạiRehashC5 · Bảng băm
Cấp một bảng lớn hơn rồi băm lại mọi khoá khi hệ số tải vượt ngưỡng, để hệ số tải không bao giờ chạm tới 1.
Mở bài dạy thuật ngữ này - Bảng bămHash tableC5 · Bảng băm
Cấu trúc đưa khoá qua một hàm số để ra chỉ số ô, nhờ đó tra cứu trung bình chỉ tốn hằng số bước thay vì phải đi tìm.
Mở bài dạy thuật ngữ này - Bảng tiền tốPrefix function tableC9 · Chuỗi
Với mỗi vị trí của mẫu, độ dài tiền tố dài nhất đồng thời cũng là hậu tố của đoạn mẫu đó. Nó cho biết khi lệch thì trượt mẫu về đâu.
Mở bài dạy thuật ngữ này - Bẫy tràn số khi lấy trung điểmMidpoint overflowC3 · Tìm kiếm
Viết trung điểm là tổng hai chỉ số chia 2 thì tràn số nguyên khi mảng rất lớn. Cách an toàn là thấp cộng nửa hiệu hai chỉ số.
Mở bài dạy thuật ngữ này - Ca cơ sởBase caseC8 · Quy hoạch động
Nhánh không gọi lại chính nó, chỗ đệ quy dừng. Thiếu nó thì hàm chạy mãi, mà có nó vẫn chạy mãi được nếu tham số bước qua nó thay vì rơi đúng vào.
Mở bài dạy thuật ngữ này - Ca xấu nhấtWorst caseC1 · Đo chi phí
Cấu hình dữ liệu vào làm giải thuật tốn nhiều phép nhất. Nó là lời hứa chắc chắn, còn trung bình chỉ là một kỳ vọng.
Mở bài dạy thuật ngữ này - Cấu trúc con tối ưuOptimal substructureC8 · Quy hoạch động
Điều kiện thứ hai: nghiệm tối ưu của bài lớn phải ghép được từ nghiệm tối ưu của các bài con. Điều này phải kiểm, không được tin.
Mở bài dạy thuật ngữ này - Cấu trúc dữ liệuData structureNhập môn
Cách tổ chức dữ liệu trong bộ nhớ. Nó quyết định thao tác nào rẻ và thao tác nào đắt, trước khi bạn viết dòng mã đầu tiên.
Mở bài dạy thuật ngữ này - Cây AVLAVL treeC6 · Cây
Cây tìm kiếm tự cân bằng, giữ hệ số cân bằng của mọi nút trong tập âm 1, 0 và 1, bằng cách xoay lại sau mỗi lần chèn hoặc xoá.
Mở bài dạy thuật ngữ này - Cây đỏ đenRed-black treeC6 · Cây
Cây tự cân bằng lỏng hơn AVL: cao hơn một chút nên tìm chậm hơn chút, đổi lại xoay ít hơn nên chèn và xoá nhanh hơn.
Mở bài dạy thuật ngữ này - Cây khung nhỏ nhấtMinimum spanning treeC7 · Đồ thị
Tập cạnh nối được mọi đỉnh mà không tạo chu trình và có tổng trọng số nhỏ nhất. Nó không phải bản đồ đường đi ngắn nhất.
Mở bài dạy thuật ngữ này - Cây thoái hoáDegenerate treeC6 · Cây
Cây mà mỗi nút chỉ có một con, tức đã thành danh sách liên kết. Chèn một dãy khoá đã sắp vào cây tìm kiếm cho đúng hình này.
Mở bài dạy thuật ngữ này - Cây tìm kiếm nhị phânBinary search treeC6 · Cây
Cây mà mọi khoá bên trái một nút đều nhỏ hơn nút đó và mọi khoá bên phải đều lớn hơn, nên tìm kiếm chỉ đi theo một đường.
Mở bài dạy thuật ngữ này - Chặn dưới của sắp xếp bằng so sánhComparison sort lower boundC4 · Sắp xếp
Không giải thuật chỉ dùng so sánh nào rẻ hơn log2 của n giai thừa được, vì mỗi phép so sánh chia số kết quả còn lại nhiều nhất làm hai.
Mở bài dạy thuật ngữ này - Chi phí khấu haoAmortized costC2 · Mảng
Chi phí trung bình mỗi thao tác khi cộng dồn cả một dãy dài. Thêm vào cuối mảng động là hằng số khấu hao, dù có lần phải chép cả mảng.
Mở bài dạy thuật ngữ này - Chỉ số con và cha trong mảngImplicit child indicesC6 · Cây
Con của ô i nằm ở 2i cộng 1 và 2i cộng 2, cha của ô i ở phần nguyên của i trừ 1 rồi chia 2. Nhờ ba phép này đống không cần con trỏ.
Mở bài dạy thuật ngữ này - Chiều cao câyTree heightC6 · Cây
Số nút trên đường dài nhất từ gốc xuống lá, nên một lá cao 1 và cây rỗng cao 0. Nó là chi phí ca xấu nhất của mọi phép tìm, chèn và xoá trên cây.
Mở bài dạy thuật ngữ này - ChốtPivotC4 · Sắp xếp
Phần tử dùng làm mốc chia mảng. Cách chọn chốt là toàn bộ khác biệt giữa n log n và bậc hai, dù phần mã còn lại không đổi.
Mở bài dạy thuật ngữ này - Dải giá trịKey rangeC4 · Sắp xếp
Số giá trị khác nhau mà khoá có thể nhận, ký hiệu k. Mảng đếm dài bằng dải này, không phải bằng số phần tử cần sắp.
Mở bài dạy thuật ngữ này - Đánh đổi thời gian và bộ nhớTime and space trade-offNhập môn
Gần như mọi cách làm nhanh hơn đều phải trả bằng ô nhớ phụ. Hỏi rẻ hơn về cái gì trước, rồi mới nói cái nào tốt hơn.
Mở bài dạy thuật ngữ này - Danh sách hai chiềuDoubly linked listC2 · Mảng
Mỗi nút giữ thêm con trỏ về nút trước. Nhờ đó xoá một nút đã nắm trong tay chỉ tốn vài phép, giá là một con trỏ trên mỗi nút.
Mở bài dạy thuật ngữ này - Danh sách kềAdjacency listC7 · Đồ thị
Mỗi đỉnh giữ danh sách các đỉnh kề nó. Tốn cỡ số đỉnh cộng số cạnh, nên nó là lựa chọn mặc định cho đồ thị thưa.
Mở bài dạy thuật ngữ này - Danh sách liên kếtLinked listC2 · Mảng
Chuỗi nút rời nhau, mỗi nút giữ dữ liệu và địa chỉ nút kế tiếp. Không ô nào nằm cạnh ô nào, nên không đọc được theo chỉ số.
Mở bài dạy thuật ngữ này - Đệ quyRecursionC8 · Quy hoạch động
Hàm tự gọi chính nó trên bài toán nhỏ hơn. Rất gọn để viết, và cũng rất dễ tính lại cùng một thứ hàng triệu lần.
Mở bài dạy thuật ngữ này - Đệ quy đuôiTail recursionC8 · Quy hoạch động
Lời gọi đệ quy là việc cuối cùng của hàm, không còn phép tính nào chờ nó về. Dạng này chuyển sang vòng lặp được mà không cần ngăn xếp phụ.
Mở bài dạy thuật ngữ này - Đếm phép tínhOperation countingC1 · Đo chi phí
Đếm chính xác số phép so sánh, phép gán và lần truy cập mảng của một đoạn mã, thay vì đoán nó nhanh hay chậm.
Mở bài dạy thuật ngữ này - Đi theo con trỏPointer chaseC2 · Mảng
Bước nhảy từ nút này sang nút kế tiếp. Muốn tới phần tử thứ k thì phải nhảy k lần, nên đọc giữa danh sách không hề tức thời.
Mở bài dạy thuật ngữ này - Điểm cắt của hai đườngCrossover pointC1 · Đo chi phí
Giá trị n mà tại đó hai đường chi phí đổi vai. Dưới nó bậc cao hơn vẫn thắng, trên nó thì bậc thấp hơn mới thắng.
Mở bài dạy thuật ngữ này - Điểm hoà vốn giữa mảng và danh sáchArray versus list break-evenC2 · Mảng
Tỉ lệ thao tác mà tại đó hai cấu trúc tốn bằng nhau. Dưới nó mảng thắng nhờ đọc theo chỉ số, trên nó danh sách thắng nhờ khỏi dời chỗ.
Mở bài dạy thuật ngữ này - Độ sâu đệ quyRecursion depthC4 · Sắp xếp
Số tầng lời gọi lồng nhau đang cùng sống. Phân hoạch lệch hết cỡ đẩy độ sâu lên tới n và làm ngăn xếp vỡ.
Mở bài dạy thuật ngữ này - Độ sâu tối đaMaximum depthC8 · Quy hoạch động
Số khung cùng tồn tại lúc đông nhất. Tháp Hà Nội n tầng gọi 2^n trừ 1 lần nhưng chỉ sâu n khung, nên hai con số này phải tách rời nhau.
Mở bài dạy thuật ngữ này - Đồ thịGraphC7 · Đồ thị
Tập đỉnh cùng tập cạnh nối chúng. Nhiều bài toán thật là đồ thị đội lốt: bản đồ, mạng máy tính, phụ thuộc giữa các công việc.
Mở bài dạy thuật ngữ này - Độ thưa của đồ thịGraph densityC7 · Đồ thị
Số cạnh thật chia số cạnh tối đa. Đây là một con số tính được quyết định ma trận kề còn đáng hay đã lãng phí, không phải một cảm giác.
Mở bài dạy thuật ngữ này - Dò tuyến tínhLinear probingC5 · Bảng băm
Va chạm thì thử ô kế tiếp cho tới khi gặp ô trống. Nhanh khi bảng còn thưa, và sụp rất dốc khi bảng gần đầy.
Mở bài dạy thuật ngữ này - Đọc theo chỉ sốIndexed accessC10 · Tra cứu
Lấy phần tử thứ k mà không phải đi qua k phần tử trước nó. Chỉ mảng làm được, và đó là lý do mảng vẫn còn sống.
Mở bài dạy thuật ngữ này - ĐốngHeapC6 · Cây
Cây nhị phân gần đầy sống trong mảng, mọi nút cha đều không lớn hơn con của nó, nên gốc luôn là khoá nhỏ nhất.
Mở bài dạy thuật ngữ này - Dựng đống từ dưới lênBottom-up heapifyC6 · Cây
Dựng đống bằng cách chìm xuống từ nửa cuối mảng ngược về gốc. Cách này tốn cỡ n bước, khác bậc với việc chèn từng khoá một.
Mở bài dạy thuật ngữ này - Duyệt giữaIn-order traversalC6 · Cây
Duyệt cây theo thứ tự trái, gốc, phải. Trên cây tìm kiếm nhị phân nó luôn cho ra dãy khoá đã sắp tăng dần.
Mở bài dạy thuật ngữ này - Duyệt theo thứ tựOrdered traversalC10 · Tra cứu
Đi qua mọi khoá theo thứ tự tăng dần. Cây tìm kiếm làm được gần như miễn phí, còn bảng băm phải sắp lại từ đầu.
Mở bài dạy thuật ngữ này - Ghi nhớ kết quảMemoizationC8 · Quy hoạch động
Cách quy hoạch động từ trên xuống: vẫn viết đệ quy, nhưng tra bảng trước khi tính và ghi vào bảng sau khi tính.
Mở bài dạy thuật ngữ này - Giải thuậtAlgorithmNhập môn
Dãy bước hữu hạn biến dữ liệu vào thành kết quả. Cùng một bài toán có nhiều giải thuật, và chúng khác nhau ở số phép phải làm.
Mở bài dạy thuật ngữ này - Gom cụm sơ cấpPrimary clusteringC5 · Bảng băm
Những khoá đã dò dồn lại thành dải liền nhau, làm mọi khoá mới rơi vào dải đó phải dò qua cả dải. Đây là lý do dò tuyến tính sụp.
Mở bài dạy thuật ngữ này - Hàm bămHash functionC5 · Bảng băm
Hàm biến khoá thành một số nguyên trong khoảng số ô bảng. Nó phải rẻ để tính và phải trải khoá đều ra khắp bảng.
Mở bài dạy thuật ngữ này - Hàng đợiQueueC2 · Mảng
Cấu trúc vào trước ra trước: thêm ở một đầu và lấy ở đầu kia, nên phải theo dõi cả đầu lẫn cuối.
Mở bài dạy thuật ngữ này - Hàng đợi ưu tiênPriority queueC6 · Cây
Cấu trúc lấy ra phần tử ưu tiên nhất chứ không theo thứ tự đi vào. Cài đặt chuẩn của nó là một cái đống.
Mở bài dạy thuật ngữ này - Hàng đợi vòngCircular queueC2 · Mảng
Hàng đợi trên mảng cố định, chỉ số cuốn quanh về 0 khi chạm hết mảng, nhờ đó không phải dời phần tử sau mỗi lần lấy ra.
Mở bài dạy thuật ngữ này - Hệ số cân bằngBalance factorC6 · Cây
Chiều cao cây con trái trừ chiều cao cây con phải của một nút. Ra ngoài khoảng cho phép thì nút đó phải được xoay lại.
Mở bài dạy thuật ngữ này - Hệ số hằngConstant factorC1 · Đo chi phí
Số nhân mà ký hiệu O ném đi nhưng máy thật vẫn phải trả. Nó quyết định người thắng ở mọi n nhỏ hơn điểm cắt.
Mở bài dạy thuật ngữ này - Hệ số lớn lênGrowth factorC2 · Mảng
Số nhân sức chứa mỗi lần mảng đầy. Nhân 2 thì ít lần chép nhất, nhân 1,5 thì bỏ trống ít hơn nên nhiều thư viện thật chọn nó.
Mở bài dạy thuật ngữ này - Hệ số tảiLoad factorC5 · Bảng băm
Số khoá chia số ô bảng. Nó là biến quyết định bảng băm còn nhanh hay đã sụp, chứ không phải số khoá tính riêng.
Mở bài dạy thuật ngữ này - Hợp nhất tìm kiếmUnion-findC7 · Đồ thị
Cấu trúc trả lời hai đỉnh đã cùng một thành phần hay chưa và gộp hai thành phần lại. Nhờ nó Kruskal phát hiện chu trình rất nhanh.
Mở bài dạy thuật ngữ này - Khoảng tìm kiếmSearch intervalC3 · Tìm kiếm
Cặp chỉ số thấp và cao khoanh phần mảng còn có thể chứa khoá. Tìm nhị phân dừng đúng khi khoảng đó rỗng.
Mở bài dạy thuật ngữ này - Khoảng tìm và số vòng xấu nhấtSearch range and worst-case roundsC3 · Tìm kiếm
Với khoảng rộng n giá trị, số vòng xấu nhất là ⌊log₂ n⌋ + 1, không phải ⌈log₂ n⌉: hai công thức lệch nhau đúng tại các luỹ thừa của 2.
Mở bài dạy thuật ngữ này - Khối lượng thao tácOperation mixC10 · Tra cứu
Số lượt của từng loại thao tác trong công việc thật của bạn. Đổi khối lượng là đổi người thắng, nên nó phải là dữ liệu vào.
Mở bài dạy thuật ngữ này - Knuth Morris PrattKnuth Morris Pratt (KMP)C9 · Chuỗi
Dùng bảng tiền tố để không bao giờ lùi con trỏ văn bản, nhờ đó chi phí là độ dài văn bản cộng độ dài mẫu chứ không phải nhân.
Mở bài dạy thuật ngữ này - KruskalKruskal algorithmC7 · Đồ thị
Sắp mọi cạnh theo trọng số rồi lần lượt nhận cạnh nào không tạo chu trình. Phần khó nằm ở việc phát hiện chu trình, không ở việc sắp.
Mở bài dạy thuật ngữ này - Ký hiệu O lớnBig-O notationC1 · Đo chi phí
Cách nói dáng đường chi phí khi n lớn dần, bằng cách ném đi mọi hệ số và mọi số hạng bậc thấp hơn.
Mở bài dạy thuật ngữ này - Ký tự và byte trong tiếng ViệtCharacter versus byteC9 · Chuỗi
Một chữ tiếng Việt có dấu chiếm nhiều byte trong UTF-8, nên đếm theo byte và đếm theo ký tự cho hai con số khác nhau.
Mở bài dạy thuật ngữ này - Lần truy cập mảngArray accessC1 · Đo chi phí
Một lần đọc hoặc ghi một ô mảng. Phải đếm riêng vì bộ nhớ đệm của máy tính tiền theo số lần chạm vào bộ nhớ.
Mở bài dạy thuật ngữ này - Lấy khoá nhỏ nhấtFind minimumC10 · Tra cứu
Đọc phần tử ưu tiên nhất đang có. Đống trả về nó ngay ở gốc, còn mảng chưa sắp phải quét hết n phần tử.
Mở bài dạy thuật ngữ này - Ma trận kềAdjacency matrixC7 · Đồ thị
Bảng n nhân n, ô hàng i cột j nói có cạnh từ i tới j hay không. Trả lời tức thời câu hỏi hai đỉnh có kề nhau, giá là n bình phương ô.
Mở bài dạy thuật ngữ này - Mảng cộng dồnPrefix sum arrayC4 · Sắp xếp
Bảng đếm sau khi cộng dồn từ trái sang phải. Nó cho biết mỗi giá trị bắt đầu ở chỉ số nào trong mảng kết quả.
Mở bài dạy thuật ngữ này - Mảng độngDynamic arrayC2 · Mảng
Mảng tự lớn lên: khi hết chỗ thì hệ xin một vùng nhớ rộng hơn, chép toàn bộ phần tử sang, rồi trả vùng cũ về.
Mở bài dạy thuật ngữ này - Ngăn xếpStackC2 · Mảng
Cấu trúc vào sau ra trước: chỉ thêm và lấy ở một đầu, nên một chỉ số đỉnh là đủ để cài đặt bằng mảng.
Mở bài dạy thuật ngữ này - Ngăn xếp lời gọiCall stackC8 · Quy hoạch động
Chồng khung chứa biến cục bộ của các lời gọi đang dở. Độ sâu tối đa của chồng này mới làm tràn ngăn xếp, chứ không phải tổng số lời gọi.
Mở bài dạy thuật ngữ này - Nghịch lý ngày sinhBirthday paradoxC5 · Bảng băm
Va chạm xuất hiện sớm hơn trực giác rất nhiều: với bảng m ô thì chỉ cần cỡ căn của m khoá là va chạm đã xảy ra quá nửa số lần.
Mở bài dạy thuật ngữ này - Nối chuỗiSeparate chainingC5 · Bảng băm
Mỗi ô giữ một danh sách các khoá cùng ô. Chi phí tăng từ từ theo hệ số tải, và bảng vẫn chạy được khi hệ số tải vượt 1.
Mở bài dạy thuật ngữ này - Nổi lên và chìm xuốngSift up and sift downC6 · Cây
Hai phép sửa lại đống: khoá mới chèn thì nổi lên phía gốc, khoá đưa từ cuối về gốc thì chìm xuống. Mỗi phép tốn nhiều nhất log n bước.
Mở bài dạy thuật ngữ này - Ô nhớ phụAuxiliary spaceC4 · Sắp xếp
Bộ nhớ ngoài mảng đầu vào mà giải thuật cần thêm. Sắp xếp trộn cần n ô, còn sắp xếp nhanh chỉ cần ngăn xếp đệ quy.
Mở bài dạy thuật ngữ này - Phân hoạchPartitionC4 · Sắp xếp
Một lượt sắp lại mảng sao cho mọi khoá nhỏ hơn chốt nằm bên trái và mọi khoá lớn hơn nằm bên phải. Nó làm đúng một việc đó.
Mở bài dạy thuật ngữ này - Phép gánAssignmentC1 · Đo chi phí
Một lần ghi giá trị vào biến hoặc vào ô mảng. Khi khoá là bản ghi lớn thì một phép gán đắt hơn một phép so sánh nhiều lần.
Mở bài dạy thuật ngữ này - Phép so sánhComparisonC1 · Đo chi phí
Một lần đối chiếu hai khoá để biết cái nào lớn hơn. Đây là đơn vị đếm chuẩn của mọi giải thuật sắp xếp và tìm kiếm.
Mở bài dạy thuật ngữ này - Phép xoayTree rotationC6 · Cây
Đổi chỗ một nút với con của nó để hạ chiều cao. Nó giữ nguyên thứ tự duyệt giữa, nên cây vẫn còn là cây tìm kiếm.
Mở bài dạy thuật ngữ này - PrimPrim algorithmC7 · Đồ thị
Lớn dần từ một đỉnh, mỗi bước nhận cạnh nhẹ nhất nối ra ngoài phần đã có. Nó cần hàng đợi ưu tiên chứ không cần hợp nhất tìm kiếm.
Mở bài dạy thuật ngữ này - Quét thẳngNaive string matchingC9 · Chuỗi
Thử mẫu ở từng vị trí của văn bản, lệch một ký tự thì dịch sang một bước và so lại từ đầu mẫu. Ca xấu nhất là số vị trí nhân độ dài mẫu.
Mở bài dạy thuật ngữ này - Quy hoạch độngDynamic programmingC8 · Quy hoạch động
Ghi lại kết quả từng bài con để không phải tính lại, nhờ đó biến một cây gọi luỹ thừa thành một bảng cỡ đa thức.
Mở bài dạy thuật ngữ này - Rabin-KarpRabin-Karp algorithmC9 · Chuỗi
So khớp chuỗi bằng cách so mã băm từng cửa sổ trước, rồi mới so ký tự ở những cửa sổ trùng băm. Trung bình nhanh, nhưng xấu nhất vẫn về bằng thuật toán thô.
Mở bài dạy thuật ngữ này - Rừng khungSpanning forestC7 · Đồ thị
Đồ thị không liên thông thì không có cây khung, chỉ có một cây khung nhỏ nhất cho từng thành phần liên thông.
Mở bài dạy thuật ngữ này - Sắp xếp chènInsertion sortC4 · Sắp xếp
Chèn từng phần tử vào đúng chỗ trong phần đã sắp phía trước. Trên mảng gần như đã sắp thì nó gần như tuyến tính.
Mở bài dạy thuật ngữ này - Sắp xếp chọnSelection sortC4 · Sắp xếp
Mỗi lượt tìm khoá nhỏ nhất trong phần chưa sắp rồi đổi nó về đúng chỗ, nên số phép đổi chỗ chỉ cỡ n dù số so sánh vẫn bậc hai.
Mở bài dạy thuật ngữ này - Sắp xếp đếmCounting sortC4 · Sắp xếp
Đếm số lần xuất hiện của từng giá trị rồi cộng dồn để biết chỗ đặt. Không dùng phép so sánh nào, chi phí là n cộng k.
Mở bài dạy thuật ngữ này - Sắp xếp nhanhQuicksortC4 · Sắp xếp
Chọn một chốt, phân hoạch mảng quanh nó, rồi đệ quy hai phía. Trung bình n log n, còn ca xấu nhất là bậc hai.
Mở bài dạy thuật ngữ này - Sắp xếp nổi bọtBubble sortC4 · Sắp xếp
Đổi chỗ hai phần tử kề nhau khi chúng nghịch thế, lặp tới khi hết nghịch thế. Số phép dời chỗ của nó cao nhất trong ba cách bậc hai.
Mở bài dạy thuật ngữ này - Sắp xếp theo cơ sốRadix sortC4 · Sắp xếp
Sắp lần lượt theo từng chữ số, từ chữ số thấp lên cao, mỗi lượt dùng một lần sắp xếp đếm. Nó chỉ đúng nếu lượt sắp đó ổn định.
Mở bài dạy thuật ngữ này - Sắp xếp trộnMerge sortC4 · Sắp xếp
Chia mảng làm đôi tới khi còn một phần tử rồi trộn ngược lên. Chi phí n log n ở cả ba ca, gần như không đọc dáng dữ liệu.
Mở bài dạy thuật ngữ này - Số nguyên tố làm số ôPrime table sizeC5 · Bảng băm
Chọn số ô là số nguyên tố để phép chia lấy dư dùng hết mọi bit của khoá, thay vì chỉ dùng vài bit thấp như khi số ô là luỹ thừa của 2.
Mở bài dạy thuật ngữ này - Sức chứaCapacityC2 · Mảng
Số ô mảng động đã xin được, luôn lớn hơn hoặc bằng số phần tử đang dùng. Phần chênh lệch là ô bỏ trống nhưng vẫn trả tiền.
Mở bài dạy thuật ngữ này - Tìm chuỗi conSubstring searchC9 · Chuỗi
Định vị mọi lần một mẫu xuất hiện trong văn bản. Đơn vị đếm ở đây là số phép so sánh ký tự, không phải số giây.
Mở bài dạy thuật ngữ này - Tìm nhị phânBinary searchC3 · Tìm kiếm
Mỗi phép so sánh loại đi một nửa khoảng còn lại, nên chi phí là log2 của n. Đổi lại nó đòi mảng phải sắp trước.
Mở bài dạy thuật ngữ này - Tìm nhị phân trên đáp ánBinary search on the answerC3 · Tìm kiếm
Chặt đôi khoảng giá trị của kết quả thay vì chặt đôi mảng dữ liệu. Dùng khi cái cần tìm là một con số chứ không phải một phần tử có sẵn.
Mở bài dạy thuật ngữ này - Tìm tuyến tínhLinear searchC3 · Tìm kiếm
Quét từ đầu tới khi gặp khoá hoặc hết mảng. Không đòi mảng đã sắp, và ca xấu nhất tốn đúng n phép so sánh.
Mở bài dạy thuật ngữ này - Tính ổn địnhStabilityC4 · Sắp xếp
Giải thuật giữ nguyên thứ tự tương đối của những khoá bằng nhau. Thiếu nó thì sắp theo nhiều tiêu chí liên tiếp cho kết quả sai.
Mở bài dạy thuật ngữ này - Tràn và rỗngOverflow and underflowC2 · Mảng
Hai ca biên phải báo ra chứ không được im lặng: thêm vào một cấu trúc đã đầy, và lấy ra từ một cấu trúc đang rỗng.
Mở bài dạy thuật ngữ này - Trộn hai dãy đã sắpMerging two sorted runsC4 · Sắp xếp
Đi song song hai dãy, mỗi bước lấy đầu nhỏ hơn. Đây là chỗ duy nhất sắp xếp trộn so sánh, và nó tốn nhiều nhất tổng độ dài hai dãy.
Mở bài dạy thuật ngữ này - Trung vị của baMedian of threeC4 · Sắp xếp
Lấy chốt là trung vị của phần tử đầu, giữa và cuối, để mảng đã sắp thôi là ca xấu nhất. Giá là vài phép so sánh thêm mỗi lượt.
Mở bài dạy thuật ngữ này - Va chạmHash collisionC5 · Bảng băm
Hai khoá khác nhau cùng ra một ô. Không tránh được khi số khoá vượt số ô, nên bảng băm phải có sẵn cách xử lý.
Mở bài dạy thuật ngữ này - Va chạm bămWindow hash collisionC9 · Chuỗi
Hai cửa sổ khác nhau cho cùng một mã băm. Vì nó luôn có thể xảy ra, Rabin-Karp buộc phải so ký tự để xác nhận: băm khớp không có nghĩa là chuỗi khớp.
Mở bài dạy thuật ngữ này - Vị trí chènInsertion pointC3 · Tìm kiếm
Chỉ số mà một khoá không tìm thấy sẽ phải nằm vào để mảng vẫn sắp. Tìm nhị phân biết nó miễn phí nhưng ít API trả nó về.
Mở bài dạy thuật ngữ này - Vị từ đơn điệuMonotone predicateC3 · Tìm kiếm
Hàm trả lời được hay không mà một khi đã đúng thì mọi giá trị lớn hơn cũng đúng. Đây mới là điều kiện để tìm nhị phân dùng được, không phải chuyện mảng đã sắp.
Mở bài dạy thuật ngữ này
Bảng này chứa gì và không chứa gì
Đây là vốn từ của riêng học phần này, không phải từ điển của cả ngành. Mỗi mục có mặt ở đây vì nó xuất hiện trong một bài của sách, và cả 102 mục đều dẫn tới một trong 24 bài đó. Ngược lại, một thuật ngữ cấu trúc dữ liệu hoàn toàn chính thống mà sách chưa dạy thì sẽ không tìm thấy ở đây, và đó là chủ ý chứ không phải thiếu sót: một bảng tra dẫn tới bài dạy chỉ có nghĩa khi bài dạy có thật.
Bảng cũng không phải một bảng chọn cấu trúc. Nó nói Bảng băm là gì, không nói bạn nên dùng bảng băm hay cây tìm kiếm. Câu hỏi nên dùng cái nào phụ thuộc khối lượng thao tác thật của bạn, mà khối lượng đó thì bảng tra không biết, nên nó cũng không được phép ám chỉ. Muốn xếp hạng theo số bước thì sang bài chọn cấu trúc theo thao tác bạn làm nhiều nhất.
Cổng kiểm của trang khoá cả hai chiều. Chiều thứ nhất, từng đường dẫn phải ứng với một tệp .mdx có thật trên đĩa, kiểm bằng cách đọc thẳng thư mục chứ không tin dữ liệu, vì một bảng tra dẫn tới trang lỗi còn tệ hơn là không có bảng tra. Chiều thứ hai, mỗi bài trong sách phải được ít nhất một thuật ngữ trỏ tới, để bảng không lặng lẽ cũ đi khi sách dài thêm. Cổng quét được 25 tệp bài trong thư mục của học phần, và 24 tệp được phủ: bài mỏng nhất được 3 thuật ngữ trỏ tới, bài dày nhất được 5, không bài nào bị bỏ sót. Ở mức sàn giờ có ba bài cùng được 3 mục chứ không còn một bài, nên cổng ghim cả tên chúng thay vì chỉ ghim con số 3.
Tệp thứ 25 là chính trang này, và nó được miễn trừ có ghi tên. Một thuật ngữ trỏ về đúng cái bảng thuật ngữ bạn đang mở là một liên kết vòng tròn, không dạy được gì. Nhưng miễn trừ lại là chỗ rất dễ biến thành ngăn kéo giấu bài chưa phủ, nên cổng khoá nó bằng năm khẳng định: danh sách miễn trừ phải có đúng một mục, mục đó phải là một tệp có thật trên đĩa, mục đó phải nằm trong danh sách tệp vừa quét, bỏ miễn trừ đi thì phải lộ ra đúng một bài chưa phủ chứ không phải hai, và một đường dẫn bịa thì không được tính là đã miễn trừ. Bài còn lại của chương 10, tức trang chọn cấu trúc, không được miễn trừ và có 4 thuật ngữ trỏ tới như mọi bài khác. Trang nhập môn cũng vậy: nó nhận 3 mục và không hề được ưu tiên.
Cổng còn đọc luôn sidebars.ts và bắt mười nhãn chương trong dữ liệu khớp từng chữ với mười chương thật của sách.
Phân bố theo chương, đúng như bộ lọc Chương in ra trong ngoặc: Nhập môn 3 mục, chương 1 Đo chi phí 9, chương 2 Mảng và danh sách 12, chương 3 Tìm kiếm 8, chương 4 Sắp xếp 17, chương 5 Bảng băm 10, chương 6 Cây 13, chương 7 Đồ thị 9, chương 8 Đệ quy và quy hoạch động 9, chương 9 Chuỗi 8, chương 10 Tra cứu 4. Cộng lại đúng 102, và phép cộng đó là một bất biến cổng khoá chứ không phải một con số tôi gõ vào.
Một cái bẫy đường dẫn, và vì sao nó không tự lộ ra
Docusaurus gộp một tệp trùng tên thư mục cha vào URL của thư mục đó. Ở môn C có docs/c/con-tro/con-tro.mdx, và địa chỉ thật của nó là /c/con-tro, không phải /c/con-tro/con-tro. Bằng chứng nằm trong thư mục dựng của chính kho này: có build/c/con-tro.html nằm cạnh thư mục build/c/con-tro/.
Chỗ nguy hiểm là cấu hình onBrokenLinks của dự án đặt ở mức warn, nên một liên kết rơi vào bẫy này không làm lệnh dựng thất bại. Nó chỉ in một dòng cảnh báo rồi đi tiếp, và bảng tra sẽ được xuất bản với một nút dẫn tới trang 404. Không bài nào của học phần này đặt tên trùng thư mục cha, nên địa chỉ luôn là /ctdl/<thư mục>/<tên bài>. Cổng giữ cho điều đó đúng mãi: nó quét mọi đường dẫn và báo bất kỳ đường nào có hai đoạn cuối trùng nhau, kèm một đối chứng dương chứng minh phép quét đó bắt được đúng ca con-tro/con-tro của môn C.
Núm bỏ dấu, và chỗ nó thật sự đổi kết quả
Núm Bỏ dấu không phải trang trí. Nó quyết định hai phía được so bằng cái gì: bật thì cả chuỗi bạn gõ lẫn nội dung bảng đều bị gỡ dấu và hạ hoa thường trước khi so, tắt thì chỉ hạ hoa thường. Ba truy vấn dưới đây cho thấy ba hành vi khác hẳn nhau, và bạn tự gõ lại được:
kruskal: 2 mục ở cả hai chế độ. Chuỗi thuần chữ Latin không dấu thì không có gì để gỡ, nên núm đứng im. Đây là ca mà núm trơ, và nó trơ đúng.primcũng vậy với 3 mục,avlcũng vậy với 2 mục.chu: 30 mục khi bỏ dấu, 12 mục khi giữ dấu. Cả hai đều khác 0, nên đây không phải cái công tắc tất cả hoặc không gì cả.sap xep: 11 mục khi bỏ dấu, 0 mục khi giữ dấu. Đây là ca thường gặp nhất trên bàn phím Việt. Trong 11 mục đó có 3 mục khớp qua phần định nghĩa chứ không qua tên, chẳng hạnÔ nhớ phụcó nhắc tới sắp xếp trộn và sắp xếp nhanh.
Đáng nhìn kỹ nhất là mốc giữa hai hành vi đầu, vì nó cách nhau đúng một ký tự. Gõ so s thì cả hai chế độ đều ra 11 mục, vì so s là tiền tố nguyên văn của so sánh. Gõ thêm một chữ thành so sa thì chế độ bỏ dấu vẫn 11, còn chế độ giữ dấu tụt thẳng về 0, vì chữ tiếp theo trong bảng là á chứ không phải a. Một ký tự, và núm đi từ vô nghĩa sang quyết định tất cả. Cổng khoá cả bốn con số đó, đúng trên mốc và đúng một bước sau mốc, vì một khẳng định chỉ đứng giữa hai mốc thì không thấy gì. Còn một mốc thứ hai cùng hình dạng để mốc thứ nhất không phải may mắn của một dòng dữ liệu: ca x ra 6 mục ở cả hai chế độ, còn ca xa ra 6 và 0.
Quét cả bảng thì bức tranh rõ hơn hẳn: bật bỏ dấu, gõ tên không dấu của bất kỳ mục nào trong 102 mục cũng tìm ra chính nó. Tắt bỏ dấu thì 98 trên 102 mục không còn tìm ra được bằng tên không dấu của chúng. Bốn mục sống sót là bốn cái tên thuần chữ Latin, và cổng gọi tên cả bốn ra thay vì chỉ nói còn bốn cái.
Ba mốc biên mà trang này phải xử đúng
Một bảng tra hỏng thường hỏng ở rìa chứ không hỏng ở giữa, nên ba trường hợp sau đều có khẳng định riêng:
- Chuỗi tìm rỗng trả về toàn bộ 102 mục. Khoảng trắng thuần cũng vậy: gõ ba dấu cách vẫn ra đúng 102, không phải 0.
- Chuỗi không khớp gì trả về đúng 0, và giao diện phải nói ra. Gõ
zzzqqqthì bảng không im lặng hiện một khung trắng, nó nói thẳng là 0 trên 102 và gợi ý ba cách sửa, trong đó có việc bật lại núm bỏ dấu. Mốc đó cũng được kiểm từ phía kia:sap xepzra 0 cònsap xepra 11. - Chuỗi quá dài bị cắt và được báo. Trần là 48 ký tự. Ở đúng 48 thì không có gì xảy ra, ở 49 thì chuỗi bị cắt còn 48 và một dòng cảnh báo hiện ra nói rõ đã cắt từ bao nhiêu xuống bao nhiêu. Việc kẹp nằm ở đúng một chỗ trong engine, và cổng chứng minh điều đó bằng cách đưa một chương bịa vào thẳng phần tính: nó ra 0 mục chứ không được tự sửa thành 102.
Đừng đọc trang này theo thứ tự. Khi gặp một từ lạ, gõ ba bốn chữ đầu của nó, đọc đúng một câu định nghĩa, rồi bấm vào bài dạy nếu vẫn thấy mờ. Nếu bạn đang ôn cả một chương thì đổi sang sắp xếp Theo chương và lọc đúng chương đó để thấy toàn bộ vốn từ của chương gom lại một chỗ. Nhớ hai giới hạn: bảng chỉ chứa 102 thuật ngữ đã được dạy trong 24 bài của học phần này, và nó chỉ định nghĩa chứ không khuyên chọn. Muốn biết nên dùng cấu trúc nào cho công việc của mình thì sang bài chọn cấu trúc: trang đó cộng số bước theo khối lượng thao tác bạn gõ vào, còn trang này chỉ định nghĩa. Con số bên phải thanh công cụ luôn là độ dài thật của danh sách, còn núm Bỏ dấu thì có lúc đổi kết quả từ 11 xuống 0 và có lúc không đổi gì cả, tuỳ chuỗi bạn gõ có dấu để gỡ hay không.
- 1Bạn gõ "so s" vào ô tìm kiếm và được 11 mục. Bấm tắt núm "Bỏ dấu", con số vẫn là 11. Kết luận nào đúng?
- 2Cổng kiểm của trang khẳng định "mọi bài của học phần đều có ít nhất một thuật ngữ trỏ tới". Vì sao cần chiều khẳng định này khi đã có chiều "mọi đường dẫn đều trỏ tới tệp có thật"?
- 3Ở môn C có tệp docs/c/con-tro/con-tro.mdx. Nếu một thuật ngữ trỏ tới địa chỉ /c/con-tro/con-tro thì chuyện gì xảy ra?