Tham khảo:

Hàm "Mystery(n)" sẽ trả về giá trị là r.

Độ phức tạp thời gian của chương trình này là O(n³)

Chương trình trên tính số lần lặp cần thiết để i lớn hơn n bằng cách nhân i với 2 trong mỗi lần lặp, sau đó tăng biến sum lên 1. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem xét số lần lặp của vòng while và các phép toán trong vòng lặp.

Vòng while: Vòng lặp này chạy cho đến khi i >= n, và giá trị ban đầu của i là 1. Trong mỗi lần lặp, i được nhân với 2, vậy số lần lặp là log₂(n) (vì sau mỗi lần nhân i với 2, giá trị của i sẽ gấp đôi). Ví dụ, nếu n = 1000 thì số lần lặp là log₂(1000) ≈ 10.

Các phép toán trong vòng lặp:

Phép gán i = i * 2: Đây là phép nhân, có độ phức tạp là O(1).

Phép gán sum = sum + 1: Đây là phép gán giá trị vào biến sum, có độ phức tạp là O(1).

Vậy tổng độ phức tạp thời gian của chương trình là O(log n), hay O(log₂(1000)) ≈ O(10)

Công việc của hàm là thực hiện sắp xếp.

Độ phức tạp của thuật toán là O(n²)

Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n²)

T = O(n) + O(n²) = O(n²)

Chọn đáp án A
A. Đây là chương trình đếm các số nguyên trong khoảng từ 1 đến 1000 là bội số của 3

*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²).

Đánh giá được mức đơn giản của thuật toán, từ đó tìm ra được cách giải nhanh nhất.

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ử.

tham khảo!

Hai bộ dữ liệu đầu vào có cùng kích thước của thuật toán trên nhưng có thời gian chạy khác nhau có thể là:

- Bộ dữ liệu 1: A = [2, 4, 6, 8, 10] # Có 5 phần tử Kết quả mong đợi: Tổng các số chẵn là 30

- Bộ dữ liệu 2: A = [1, 3, 5, 7, 9] # Có 5 phần tử Kết quả mong đợi: Tổng các số chẵn là 0

Trong trường hợp này, cả hai bộ dữ liệu đều có cùng kích thước là 5 phần tử, nhưng thời gian chạy của thuật toán sẽ khác nhau vì số lượng số chẵn trong dãy số khác nhau. Bộ dữ liệu 1 chứa toàn số chẵn nên thời gian chạy của thuật toán sẽ lớn hơn bộ dữ liệu 2 chỉ chứa các số lẻ.