Quan Điểm Thực Hành - Độ Phức Tạp Thuật Toán

Giả sử có 1 thuật toán A nào đó.
Trong A có 1 loại thao tác P có đặc điểm sau:

1. Tổng thời gian chạy P ảnh hưởng chủ yếu đến thời gian chạy của A.
2. P lặp đi lặp lại nhiều lần

Ta dùng P làm thao tác cơ sở, tgian thực hiện P dùng làm đơn vị đo thời gian.
Số lần thực hiện P trong giải thuật A sẽ dùng làm đại lượng đo thời gian chạy của A, đại lượng này được gọi là độ phức tạp tính toán về mặt thời gian của giải thuật A với thao tác cơ sở là P

Thông thường, P có thể là:

-    Phép gán (chuyển dữ liệu)
-    Phép cộng
-    Phép *, /, ^
-    Phép so sánh (Compare)

Ký hiệu:

-    Độ phức tạp thời gian là: M(n)    ; n là kích cỡ dữ liệu chỉ phép gán làm thao tác cơ sở
-    Độ phức tạp thời là: C(n)        ; n chỉ phép so sánh làm cơ sở
-    Độ phức tạp thời gian tổng quát: T(n)    ; n có thể là số số hạng của dãy số, có thể là độ dài xâu, có thể là số vòng lặp, có thể là kích cỡ số bit của số lớn. Vậy n của từng bài toán là khác nhau.

Chú ý: Không phải giải thuật nào cũng dễ dàng xác định được số lần thực hiện của P.
Ví dụ: Giải thuật sắp xếp dãy số

-    TH1: Nếu đã sắp xếp >> M(n) = 0
-    TH2: Nếu dãy số bị đảo ngẫu nhiên >> Không xác định được M(n)
-    Trong trường hợp 2:
+ Phải chỉ ra trường hợp xấu nhất và tốt nhất
+ Chỉ ra trung bình thô, tốt hơn nếu chỉ ra được TB xác suất.

Ví dụ:
Di = dãy số có thể có thứ i
I = {Di : tập các dãy số có thể} , n cố định
Số dịch chuyển sắp xếp lại là Mi
Di có X.S xuất hiện = Pi

Và ta có:

Phép chiếu phần lớn thời gian chạy của A & B là: P := P * (x/j);
- Phép tính P là thao tác cơ sở
- Số đo:
1. Giải thuật A: TA(n) := 1 + 2 + … + n
2. Giải thuật B: TA(n) := n
3. Giải thuật B là tốt hơn so với A (khi n lớn)

Hai hướng tiếp cận chủ đạo độ phức tạp là:

- Thời gian chạy - Time complexity (độ phức tạp thời gian tính toán giải thuật)
- Không gian nhớ - Space complexity (độ phức tạp không gian giải thuật)