Tham khảo:

QT1. Quy tắc cộng: O(f(n)+g(n))=O(max(f(n),g(n)))

QT2. Quy tắc nhân:

- Với hằng sô: O(C.f(n))=O(f(n))

- Với hàm số: O(f(n).g(n))=O(f(n)).O(g(n))

Thuật toán là một chuỗi các bước được thiết kế để giải quyết một vấn đề cụ thể. Một trong những yếu tố quan trọng để đánh giá hiệu suất của một thuật toán là độ phức tạp thời gian, tức là thời gian mà thuật toán mất để thực thi dựa trên kích thước đầu vào của vấn đề. Phân loại thuật toán dựa trên độ phức tạp thời gian là một phương pháp được sử dụng phổ biến để đánh giá và so sánh hiệu suất của các thuật toán khác nhau. Dưới đây là một số phân loại chính dựa trên độ phức tạp thời gian của thuật toán:

-O(1) (độ phức tạp thời gian hằng số): Đây là loại thuật toán có thời gian thực thi không thay đổi theo kích thước đầu vào. Thời gian thực thi của thuật toán này là cố định, vì vậy độ phức tạp thời gian là hằng số. Ví dụ: Truy cập vào phần tử trong mảng có kích thước cố định.

-O(log n) (độ phức tạp thời gian logarithmic): Đây là loại thuật toán có thời gian thực thi tăng theo logarit của kích thước đầu vào. Thuật toán này thường được sử dụng trong các bài toán tìm kiếm nhị phân, các thuật toán chia để trị, hoặc các thuật toán sắp xếp hiệu quả như QuickSort hoặc MergeSort.

-O(n) (độ phức tạp thời gian tuyến tính): Đây là loại thuật toán có thời gian thực thi tăng tỷ lệ trực tiếp với kích thước đầu vào. Ví dụ: Duyệt qua từng phần tử trong mảng một lần.

-O(n²) (độ phức tạp thời gian bậc hai): Đây là loại thuật toán có thời gian thực thi tăng theo bình phương của kích thước đầu vào. Ví dụ: Thuật toán sắp xếp Bubble Sort, các thuật toán tìm kiếm không hiệu quả như Linear Search trong một mảng lồng nhau.

-O(n^k) (độ phức tạp thời gian bậc k): Đây là loại thuật toán có thời gian thực thi tăng theo lũy thừa của kích thước đầu

Hai tiêu chí đánh giá độ phức tạp tính toán quan trọng nhất là:

1. Thời gian thực thi (Runtime): Đây là thời gian mà chương trình hoặc thuật toán mất để thực hiện một nhiệm vụ hoặc tính toán. Thời gian thực thi là một tiêu chí quan trọng vì nó đo lường tốc độ hoạt động của chương trình, và đối với các ứng dụng yêu cầu xử lý dữ liệu lớn hoặc thực hiện tính toán phức tạp, thời gian thực thi càng nhanh thì chương trình càng hiệu quả.

2. Độ phức tạp không gian (Space complexity): Đây là lượng bộ nhớ mà chương trình hoặc thuật toán sử dụng trong quá trình thực hiện nhiệm vụ hoặc tính toán. Độ phức tạp không gian cũng là một tiêu chí quan trọng vì nó đo lường khả năng sử dụng tài nguyên bộ nhớ của chương trình, và đối với các ứng dụng có yêu cầu về tài nguyên hạn chế, độ phức tạp không gian càng thấp thì chương trình càng hiệu quả.

tính E(300)=300/log2(300), E(90000)=90000/log2(90000)

Vì độ hiệu quả tỉ lệ thuận với thời gian thực hiện

nên ta có tỉ số 0,02/E(300)=x/E(90000) (x là giá trị cần tìm).

Từ đó tính được x=3

Sau lần chia đôi đầu tiên, pham vi tìm kiếm còn lại n/2 số, sau khi chia đôi lần thứ hai, dãy còn lại n/4 số, sau khi chia đôi lần thứ dãy còn lại n/8, …sau khi chia đôi lần k dãy còn lại n/2.­­­­­­­mũ k. Kết thúc khi 2 mũ k sấp xỉ n.

1. Tính số lần lặp của vòng lặp bên trong của thuật toán sắp xếp chèn tuyến tính.

2. Tính số lần lặp của vòng lặp ngoài của thuật toán sắp xếp chèn tuyến tính.

3. Ước lượng độ phức tạp thời gian của thuật toán sắp xếp chèn tuyến tính:

Vòng lặp for bên ngoài kiểm soát việc thực hiện đúng n-1 bước.

Vòng lặp while lồng bên trong thực hiện đồng thời cùng lúc hai việc a) và b) theo cách dịch chuyển dần từng bước sang trái, từ vị trí i tới vị trí k+1

*Chương trình 1:

from collections import Counter

import time

n = 1000

c = 0

# Ghi lại thời điểm bắt đầu

start_time = time.time()

for k in range(n):

  c = c + 1

# Ghi lại thời điểm kết thúc

end_time = time.time()

# Tính thời gian hoàn thành

elapsed_time = end_time - start_time

# Sử dụng hàm Counter để đếm số lần lặp

counter = Counter(range(n))

# In số lần lặp

print("Số lần lặp: {}".format(counter))

# In thời gian thực thi

print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time))

*Chương trình 2:

import time

n = 1000

c = 0

# Ghi lại thời điểm bắt đầu

start_time = time.perf_counter()

for k in range(n):

 for j in range(n):

  c = c + 1

# Ghi lại thời điểm kết thúc

end_time = time.perf_counter()

# Tính thời gian hoàn thành

elapsed_time = end_time - start_time

# In số lần lặp

print("Số lần lặp: {}".format(c))

# In thời gian thực thi

print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time))

→Sự khác biệt độ phức tạp thời gian của 2 chương trình trên:

Độ phức tạp thời gian của chương trình 1 là O(1), còn độ phức tạp thời gian của chương trình 2 là O(n²).

Số lần so sánh giữa các phần tử: Trong thuật toán sắp xếp chọn, số lần so sánh giữa các phần tử là cố định, không phụ thuộc vào dữ liệu đầu vào. Cụ thể, số lần so sánh trong thuật toán sắp xếp chọn là \(\dfrac{n\left(n-1\right)}{2}\), với n là số phần tử trong mảng hoặc danh sách.

Số lần hoán đổi giữa các phần tử: Trong thuật toán sắp xếp chọn, số lần hoán đổi giữa các phần tử có thể đạt đến tối đa n-1 lần, với n là số phần tử trong mảng hoặc danh sách.

Vậy độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n²), hay \(\dfrac{n\left(n-1\right)}{2}\) lần so sánh và tối đa n-1 lần hoán đổi giữa các phần tử.