Cách tính độ phức tạp của một giải thuật bất kỳ là một vấn đề không đơn giản. Tuy nhiên ta có thể tuân theo một số nguyên tắc sau:
Qui tắc cộng
Nếu T1[n] và T2[n] là thời gian thực hiện của hai đoạn chương trình P1 và P2; và
T1[n]=O[f[n]], T2[n]=O[g[n]] thì thời gian thực hiện của đoạn hai chương trình đó
nối tiếpnhaulà T[n]=O[max[f[n],g[n]]]
Lệnh gán x:=15 tốn một hằng thời gian hay O[1], Lệnh đọc dữ liệu
READ[x] tốn một hằng thời gian hay O[1]. Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là O[max[1,1]]=O[1]
Qui tắc tổng quát để phân tích một chương trình
Thời gian thực hiện của mỗi lệnh gán, READ, WRITE là O[1].
Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng qui tắc cộng. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh.
Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là O[1].
Thời gian thực hiện vòng lặp là tổng [trên tất cả các lần lặp] thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp.
Tính thời gian thực hiện của thủ tục sắp xếp nổi bọt
PROCEDURE Bubble[VAR a: ARRAY[1..n] OF integer]; VAR i,j,temp: Integer; BEGIN {1} FOR i:=1 TO n-1 DO {2} FOR j:=n DOWNTO i+1 DO {3} IF a[j-1]>a[j]THEN BEGIN{hoán vị a[i], a[j]} {4} temp := a[j-1]; {5} a[j-1] := a[j]; {6} a[j] := temp; END; END;Về giải thuật sắp xếp nổi bọt, chúng ta sẽ bàn kĩ hơn trong chương 2. Ở đây, chúng ta chỉ quan tâm đến độ phức tạp của giải thuật.
Ta thấy toàn bộ chương trình chỉ gồm một lệnh lặp {1}, lồng trong lệnh {1} là lệnh
{2}, lồng trong lệnh {2} là lệnh {3} và lồng trong lệnh {3} là 3 lệnh nối tiếp nhau
{4}, {5} và {6}. Chúng ta sẽ tiến hành tính độ phức tạp theo thứ tự từ trong ra.
Trước hết, cả ba lệnh gán {4}, {5} và {6} đều tốn O[1] thời gian, việc so sánh a[j-1] >
a[j] cũng tốn O[1] thời gian, do đó lệnh {3} tốn O[1] thời gian.
Vòng lặp {2} thực hiện [n-i] lần, mỗi lần O[1] do đó vòng lặp {2} tốn O[[n-i].1] = O[n-i].Vòng lặp {1} lặp có I chạy từ 1 đến n-1nên thời gian thực hiện của vòng lặp
{1} và cũng là độ phức tạp của giải thuật là:
Chú ý: Trong trường hợp vòng lặp không xác định được số lần lặp thì chúng ta phải lấy số lần lặp trong trường hợp xấu nhất.
Tìm kiếm tuần tự. Hàm tìm kiếm Search nhận vào một mảng a có n số nguyên và một số nguyên x, hàm sẽ trả về giá trị logic TRUE nếu tồn tại một phần tử a[i] = x, ngược lại hàm trả về FALSE.
Giải thuật tìm kiếm tuần tự là lần lượt so sánh x với các phần tử của mảng a, bắt đầu từ a[1], nếu tồn tại a[i] = x thì dừng và trả về TRUE, ngược lại nếu tất cả các phần tử của a đều khác X thì trả về FALSE.
FUNCTION Search[a:ARRAY[1..n] OF Integer;x:Integer]:Boolean; VAR i:Integer; Found:Boolean; BEGIN {1} i:=1; {2} Found:=FALSE; {3} WHILE[i