Độ phức tạp thời gian của thuật toán được biểu diễn như thế nào?

DAA-Test L2

Quiz
•
Computers
•
University
•
Easy
Nguyen Thi Hong Minh
Used 1+ times
FREE Resource
10 questions
Show all answers
1.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Một hằng số
Một biến
Một hàm của kích thước dữ liệu vào
Một giá trị đo được
Answer explanation
Độ phức tạp thời gian mô tả sự tăng trưởng của thời gian thực hiện thuật toán khi kích thước dữ liệu đầu vào tăng lên. Nó được biểu diễn bằng một hàm toán học, thường là hàm của biến n (kích thước dữ liệu vào).
2.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Đánh giá thời gian thực hiện thuật toán bằng phương pháp thực nghiệm là gì?
Phân tích code để tìm ra độ phức tạp
Chạy thuật toán với dữ liệu khác nhau và đo thời gian
Sử dụng các công cụ toán học để ước tính thời gian
Dự đoán thời gian chạy dựa trên kinh nghiệm
Answer explanation
Đánh giá thực nghiệm là chạy thuật toán trên máy tính với các bộ dữ liệu khác nhau và đo thời gian thực hiện. Phương pháp này cho kết quả trực quan, nhưng phụ thuộc vào phần cứng và dữ liệu thử nghiệm.
3.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Chứng minh tính đúng của thuật toán là gì?
Chạy thử thuật toán với nhiều dữ liệu
Kiểm tra kết quả của thuật toán
Chứng minh bằng lý luận logic rằng thuật toán luôn cho kết quả đúng
So sánh thuật toán với các thuật toán khác
Answer explanation
Chứng minh tính đúng đắn là quá trình sử dụng các phương pháp toán học và logic để chứng minh rằng thuật toán sẽ luôn hoạt động đúng như mong đợi, bất kể dữ liệu đầu vào là gì.
4.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Phương pháp nào thường được sử dụng để chứng minh tính đúng của thuật toán lặp?
Phản chứng
Trực giác
Quy nạp
Bất biến vòng lặp
Answer explanation
Bất biến vòng lặp là một mệnh đề đúng trước, trong và sau mỗi lần lặp của vòng lặp. Bằng cách chứng minh bất biến đúng và kết hợp với điều kiện dừng của vòng lặp, ta có thể chứng minh tính đúng của thuật toán lặp.
5.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Thuật toán có độ phức tạp O(n²) sẽ mất bao lâu để xử lý dữ liệu gấp đôi kích thước?
Gấp đôi thời gian
Gấp đôi thời gian
Gấp bốn thời gian
Không thay đổi
Answer explanation
Kích thước dữ liệu vào ảnh hưởng tới hàm đánh giá độ phức tạp theo bậc của hàm.
6.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Để chứng minh tính đúng của một thuật toán, ta cần chỉ ra:
Thuật toán luôn nhanh hơn các thuật toán khác
Thuật toán trả về kết quả đúng cho mọi đầu vào hợp lệ
Thuật toán chắc chắn dừng
Thuật toán sử dụng ít bộ nhớ nhất
Answer explanation
Chứng minh tính đúng của thuật toán là sử dụng các kĩ thuật phù hợp để chỉ ra rằng thuật toán sẽ cho ra kết quả đúng với mọi dữ liệu đầu vào.
7.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Thuật toán đệ quy là gì?
Một thuật toán gọi chính nó với đầu vào nhỏ hơn
Một thuật toán không bao giờ lặp lại
Một thuật toán sử dụng vòng lặp thay vì hàm
Một thuật toán chỉ hoạt động với đầu vào cố định
Answer explanation
Bài toán đệ quy là bài toán có lời giải được xác định thông qua lời giải của bài toán tương tự chính nó, nhưng với bộ tham số "đơn giản" hơn. Thuật toán đệ quy giải bài toán đệ quy nên có lời gọi tới chính thuật toán đó với tham số đầu vào nhỏ hơn, đơn giản hơn.
Create a free account and access millions of resources
Similar Resources on Quizizz
10 questions
UDCNTT

Quiz
•
University
10 questions
KT 15 PHÚT TIN 6 - HKII(L2)

Quiz
•
7th Grade - University
14 questions
BÀI 14- THUẬT TOÁN TÌM KIẾM TUẦN TỰ

Quiz
•
6th Grade - University
12 questions
Ngôn ngữ Lập trình

Quiz
•
University
15 questions
Quiz 2

Quiz
•
University
10 questions
G6.F1. Thuật toán

Quiz
•
6th Grade - University
10 questions
Kiểm tra thường xuyên

Quiz
•
University
10 questions
Khám phá máy tính lớp 5

Quiz
•
10th Grade - Professi...
Popular Resources on Quizizz
15 questions
Multiplication Facts

Quiz
•
4th Grade
25 questions
SS Combined Advisory Quiz

Quiz
•
6th - 8th Grade
40 questions
Week 4 Student In Class Practice Set

Quiz
•
9th - 12th Grade
40 questions
SOL: ILE DNA Tech, Gen, Evol 2025

Quiz
•
9th - 12th Grade
20 questions
NC Universities (R2H)

Quiz
•
9th - 12th Grade
15 questions
June Review Quiz

Quiz
•
Professional Development
20 questions
Congruent and Similar Triangles

Quiz
•
8th Grade
25 questions
Triangle Inequalities

Quiz
•
10th - 12th Grade