Độ phức tạp thuật toán

Độ phức tạp thuật toán

  1. Định nghĩa
    • Thời gian thực hiện một giải thuật bằng chương trình máy tính phụ thuộc vào:
      1. Kích thước dữ liệu đầu vào: Dữ liệu càng lớn thì thời gian xử lí càng lâu
      2. Tốc độ xử lí của máy tính: yếu tố này sẽ không ảnh hưởng nếu xem xét dựa trên độ dài dữ liệu
    • Từ đó, Độ phức tạp thuật toán là số lần thực hiện phép toán tích cực, với phép toán tích cực là phép toán thực hiện nhiều nhất với thuật toán đó
      Hơi khó hình dung VD: for(int i=1;i<=n;i+=) sum+=i;
      Phép toán tích cực là thực hiện n lần phép cộng sum=sum+i. Từ đó, độ phức tạp là 1 lần thực hiện phép toán tích cực đó
  2. Các dạng hàm đánh giá độ phức tạp của thuật toán
    Dạng đánh giá Tên gọi
    O(1) Hằng số
    O(n) Tuyến tính
    O(lg log n Log log
    O(log) Logarithm
    O(n2) Bậc 2
    O(n3) Bậc 3
    O(nm) Đa thức
    O(mn) Số mũ
    O(n!) Giai thừa
  3. Các quy tắc xác định độ phức tạp thuật toán
    1. Quy tắc tổng: f1(x) có độ phức tạp là O(g1(x)) và f2(x) có độ phức tạp là O(g2(x)) thì Độ phức tạp f(f1(x)+f2(x)) là Max(O(g1(x)),O(g2(x)))
    2. Quy tắc nhân: f(x) có độ phức tạp là O(g(x)) thì Độ phức tạp f n(x)là O(gn(x))
  4. Ví dụ
    Dạng đánh giá Ví dụ
    O(1)
    Không chứa vòng lặp hoặc vòng lặp chỉ tăng giảm theo Hằng số    		 
    For(int i=0;i<=n;i++){     
    Code có độ phức tạp O(1)
}
    O(n)
    Vòng lặp tăng giảm theo Tham số C    		 
    For(int i=0;i<=n;i+=c){     
    Code có độ phức tạp O(1)
}
    O(n2)
    Vòng lặp lồng nhau với độ phức tạp là số lần lồng nhau của các vòng lặp    		 
    For(int i=0;i<=n;i+=c){     
    for(int j=0;j<=m;j++){
            Code có độ phức tạp O(1)
}}
    O(lg(n))
    Vòng lặp chia hoặc nhân với tham số C    		 
    For(int i=0;i<=n;i*=c){     
    Code có độ phức tạp O(1)
}
    O(lg(lg(n)))
    Vòng lặp tăng hoặc giảm với hàm mũ hoặc Log(    		 
    For(int i=0;i<=n;i*=pow(2,c)){     
    Code có độ phức tạp O(1)
}