Tính giá trị biểu thức hậu tố

Duyệt biểu thức từ trái sang phải nếu gặp toán hạng thì đưa giá trị vào ngăn xếp , nếu gặp phép toán thì thực hiện hai phép toán này với hai toán hạng được lấy ra từ ngăn xếp , cất giữ giá trị vào ngăn xếp , tiếp tục duyệt cho đến khi giá trị chỉ còn một giá trị duy nhất - chính là giá trị biểu thức

Chuyển biểu thức dạng trung tố sang hậu tố

Ta duyệt biểu thức từ trai qua phải , khi gặp toán hạng đưa nó ra

Nếu phép toán đang xét có thứ tự ưu tiên thấp hơn so với phép toán ở đầu ngăn xếp , thì phép toán ở đầu ngăn xếp phải dời ngăn xếp

Cùng mức yêu tiên

Nếu phếp toán có tính kết hợp trái thì phép toán ở đỉnh ngăn xếp cần đưa ra

Nếu phép toán kết hợp phải . thì không đưa phép toán ở đỉnh ngăn xếp ra

Duyệt cây

Thứ tự trước : ta đưa ra nút khi đi qua nó

Thứ tự sau : ta đưa ra nút khi qua nó ở lần cuối trước khi quay về cha của nó

Thứ tự giữa : ta đưa ra lá khi đi qua nó, còn những nút trong được đưa ra khi đi qua nó lần 2

Sắp xếp

Sắp xếp chèn là tại chỗ và ổn định

Tôt nhất 0 hoán đổi n-1 so sánh , TB n^2/4 hoán đổi và so sánh , xấu nhất n^2/2 hoán đổi và so sánh

Sắp xếp lựa chọn

Tôt nhất 0 đổi chỗ n^2/2 so sánh , TB O(n) đổi chỗ n^2/2 so sánh , xấu nhất n-1 đổi chỗ n^2/2 so sánh

Sắp xếp nổi bọt

Tôt nhất 0 đổi chỗ n^2/2 so sánh , TB n^2/4 đổi chỗ n^2/2 so sánh , xấu nhất n^2/2 đổi chỗ n^2/2 so sánh

Sắp xếp trộn

T(n) = 2t(n/2) + n

T(n) = nlogn

Sắp xếp nhanh

Xấu nhất O(n^2)

Tốt nhất nlog(n)

Sắp xếp vun đống

Max heapify O(logn)

Bild Max heap O(n)

Heap sort O(nlogn)

Max heap insert O(logn)

Heap extract max O(logn)

Heap increase O(logn)

Heap maximum O(1)