Câu hỏi:
13/07/2024 419
Xác định độ phức tạp của thuật toán sắp xếp nổi bọt sau:
def BubbleSort(A):
n = len(A)
for i in range(n-1):
for j in range(n-1-i):
if A[j] > A[j+1]:
A[j],A[j+1] = A[j+1]1,A[j]
Xác định độ phức tạp của thuật toán sắp xếp nổi bọt sau:
def BubbleSort(A):
n = len(A)
for i in range(n-1):
for j in range(n-1-i):
if A[j] > A[j+1]:
A[j],A[j+1] = A[j+1]1,A[j]
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n2)
T=O(n)+O(n2)=O(n2)
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Giả sử rằng mỗi phép tính đơn được thực hiện trong micro giây (1 us = một phần triệu giây). Hãy xác định giá trị lớn nhất của n trong các thuật toán tìm kiếm tuần tự, sắp xếp chèn và sắp xếp chọn nếu thời gian thực thi các thuật toán là 1 giây, 1 phút và 1 giờ?
Giả sử rằng mỗi phép tính đơn được thực hiện trong micro giây (1 us = một phần triệu giây). Hãy xác định giá trị lớn nhất của n trong các thuật toán tìm kiếm tuần tự, sắp xếp chèn và sắp xếp chọn nếu thời gian thực thi các thuật toán là 1 giây, 1 phút và 1 giờ?
Xem đáp án »
20/04/2023
466
Câu 2:
Cho biết hàm sau sẽ trả về giá trị là bao nhiêu? Xác định độ phức tạp thời gian O- lớn của chương trình.
def Mystery(n):
r=0
for i in range(n-1):
for j in range(i+1,n):
for k in range(1,j):
r=r+1
return r
Cho biết hàm sau sẽ trả về giá trị là bao nhiêu? Xác định độ phức tạp thời gian O- lớn của chương trình.
def Mystery(n):
r=0
for i in range(n-1):
for j in range(i+1,n):
for k in range(1,j):
r=r+1
return r
Xem đáp án »
11/07/2024
245
Câu 3:
Biết cách phân tích, đánh giá độ phức tạp thuật toán là kĩ năng quan trọng của người thiết kế thuật toán và chương trình. Các quy tắc đơn giản tính độ phức tạp thời gian mang lại cho em điều gì khi đánh giá thuật toán?
Biết cách phân tích, đánh giá độ phức tạp thuật toán là kĩ năng quan trọng của người thiết kế thuật toán và chương trình. Các quy tắc đơn giản tính độ phức tạp thời gian mang lại cho em điều gì khi đánh giá thuật toán?
Xem đáp án »
13/07/2024
166
Câu 4:
Hãy cho biết hàm sau thực hiện công việc gì? Xác định độ phức tạp thời gian của thuật toán.
def func(A):
n=len(A)
for i in range(n-1):
for j in range(i+1,n):
if A[j] > A[j]:
A[j],A[j] = A[j],A[i]
Hãy cho biết hàm sau thực hiện công việc gì? Xác định độ phức tạp thời gian của thuật toán.
def func(A):
n=len(A)
for i in range(n-1):
for j in range(i+1,n):
if A[j] > A[j]:
A[j],A[j] = A[j],A[i]
Xem đáp án »
20/04/2023
162
về câu hỏi!