Tôi muốn biết phức tạp thời gian chạy trường hợp xấu nhất của câu lệnh chuyển đổi là gì, giả sử bạn có n trường hợp.Độ phức tạp thời gian chạy của câu lệnh switch là gì?
Tôi luôn cho rằng đó là O (n). Tôi không biết nếu trình biên dịch làm bất cứ điều gì thông minh, mặc dù. Nếu câu trả lời là thực hiện cụ thể, tôi muốn biết các ngôn ngữ sau:
Đó là lúc tồi tệ nhất O (n). Đôi khi (và điều này là phụ thuộc vào ngôn ngữ và trình biên dịch), nó chuyển thành tra cứu bảng nhảy (đối với các công tắc "đẹp" không có phạm vi trường hợp quá lớn). Sau đó, đó là O (1).
Nếu trình biên dịch muốn trở nên sôi nổi, tôi có thể nghĩ cách phức tạp có thể được triển khai để làm bất kỳ điều gì ở giữa (ví dụ: thực hiện tìm kiếm nhị phân trên các trường hợp, đối với logn). Nhưng trong thực tế, bạn sẽ nhận được thời gian tuyến tính eiher hoặc thời gian liên tục.
Độ phức tạp lớn của lệnh chuyển đổi không thực sự là điểm quan trọng. Ký hiệu Big-O đề cập đến hiệu suất khi n tăng theo hướng vô cùng. Nếu bạn có một tuyên bố chuyển đổi đủ lớn mà hiệu suất tiệm cận là một vấn đề thì nó quá lớn và nên được tái cấu trúc.
Ngoài vấn đề về khả năng đọc, trong Java và C# Tôi nghĩ bạn sẽ sớm đạt được một số giới hạn nội bộ cho kích thước tối đa của một phương thức.
Đối với các câu lệnh chuyển đổi tương đối nhỏ được gọi thường xuyên, có lẽ sẽ có nhiều thông tin hơn để đo lường hiệu suất thực tế của câu lệnh chuyển đổi so với các cách tiếp cận khác mà bạn có thể sử dụng thay thế. Phép đo này có thể được thực hiện bằng cách lặp lại thực hiện thao tác trong một vòng lặp.
Để có báo cáo chuyển đổi lớn hơn, tôi khuyên bạn nên tái cấu trúc để sử dụng từ điển hoặc cấu trúc dữ liệu tương tự có khoảng O (1) hiệu suất thậm chí có n rất lớn và nó sẽ không gặp sự cố với kích thước phương thức có giới hạn.
Nếu câu lệnh chuyển đổi 10 trường hợp được gọi là đủ thường xuyên, sẽ không có ý nghĩa để cố gắng hiểu nó hoạt động như thế nào trong nội bộ? – Fragsworth
Tôi hoàn toàn đồng ý. Khi bạn nhận được tối đa 10 trường hợp, bạn nhanh chóng mất khả năng đọc và đơn giản. Thường có một cách tốt hơn, rõ ràng hơn để đi về mọi thứ. –
@Fragsworth vâng, bạn chắc chắn nên cố gắng hiểu cách hoạt động bên trong. Nhưng điều duy nhất mà Big-O nói với bạn là nó sẽ nhanh như thế nào với LOTS, 100+. Điểm của Mark là có nhiều cách tốt hơn để phân tích các bảng báo cáo của switch mà không cần nhìn vào O-big của nó, giống như cách trình biên dịch tối ưu hóa nó và cách nó sẽ so sánh với các phương thức khác như bảng tra cứu. –
Trình biên dịch C++ có thể chuyển các câu lệnh chuyển đổi thành bảng nhảy (tức là xây dựng một dãy số dời nhảy, sau đó lấy giá trị và sử dụng nó làm chỉ mục trong bảng). Đây là O (1).
Trình biên dịch C# sử dụng cách tiếp cận tương tự, ngoại trừ việc nó có thể lắp ráp một bảng băm.
Trường hợp xấu nhất có thể là O (n), nhưng ít nhất đối với các ngôn ngữ như C/C++, Java và C# trong đó các trường hợp là hằng số biên dịch thời gian, thường có thể sử dụng bảng nhảy (và thường được sử dụng) để có được sự phức tạp đối với O (1).
Tôi không biết liệu các ngôn ngữ động hơn như PHP hay Javascript có cố gắng thiết lập bảng nhảy hay không.
Đối với php, biểu thức ca không cần phải là hằng số; 'switch (true) {case expr: doSomething(); } 'là hợp lệ, ngay cả khi expr không phải là hằng số. Đó là, nếu tôi nhớ chính xác. Vì vậy, nhảy bảng sẽ không có khả năng cho một cái gì đó như thế. – user314104
C với trình biên dịch gcc có O (1) cho phạm vi chặt chẽ (nhảy bảng) hoặc tại O tồi tệ nhất (log N) cho phạm vi rộng (tìm kiếm nhị phân).
Câu trả lời không chỉ là ngôn ngữ cụ thể, thậm chí không phải là trình biên dịch cụ thể. Nó phụ thuộc vào mã thực tế. Một số câu lệnh switch được chuyển thành các bảng nhảy bởi một số trình biên dịch. –
Ở thái cực khác, các giá trị có thể khiến các chức năng khác được gọi. Trong Ruby, ví dụ, các giá trị được kiểm tra bằng toán tử '===', có thể làm bất cứ điều gì. Một cách sử dụng phổ biến của điều này là biểu thức thông thường, trong đó (trong một số trường hợp) có thể rất tốn kém - vì vậy chi phí chuyển đổi bị chi phối bởi chính các giá trị, chứ không phải bởi số lượng có. – Ken
Có tình huống nào có thể lớn hơn * so với O (n) (đối với các trường hợp * n * trong chuyển đổi) không? – FrustratedWithFormsDesigner