Độ 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 Wayground
5 questions
Đệ quy

Quiz
•
University
10 questions
TIN 10 BAI 6

Quiz
•
12th Grade - University
10 questions
TIN 10 BAI 4

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

Quiz
•
6th Grade - University
10 questions
Câu hỏi về thuật toán tìm kiếm tuần tự

Quiz
•
9th Grade - University
15 questions
Quiz 2

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

Quiz
•
6th Grade - University
10 questions
Tin 8 - 15p SỐ 1

Quiz
•
8th Grade - University
Popular Resources on Wayground
25 questions
Equations of Circles

Quiz
•
10th - 11th Grade
30 questions
Week 5 Memory Builder 1 (Multiplication and Division Facts)

Quiz
•
9th Grade
33 questions
Unit 3 Summative - Summer School: Immune System

Quiz
•
10th Grade
10 questions
Writing and Identifying Ratios Practice

Quiz
•
5th - 6th Grade
36 questions
Prime and Composite Numbers

Quiz
•
5th Grade
14 questions
Exterior and Interior angles of Polygons

Quiz
•
8th Grade
37 questions
Camp Re-cap Week 1 (no regression)

Quiz
•
9th - 12th Grade
46 questions
Biology Semester 1 Review

Quiz
•
10th Grade